Tender Carpenter
Contest: Good Bye 2024: 2025 is NEAR
Difficulty rating: 800
Tags: dp, geometry, greedy, math

In his dream, Cocoly would go on a long holiday with no worries around him. So he would try out for many new things, such as... being a carpenter. To learn it well, Cocoly decides to become an apprentice of Master, but in front of him lies a hard task waiting for him to solve.

Cocoly is given an array $$$a_1, a_2,\ldots, a_n$$$. Master calls a set of integers $$$S$$$ stable if and only if, for any possible $$$u$$$, $$$v$$$, and $$$w$$$ from the set $$$S$$$ (note that $$$u$$$, $$$v$$$, and $$$w$$$ do not necessarily have to be pairwise distinct), sticks of length $$$u$$$, $$$v$$$, and $$$w$$$ can form a non-degenerate triangle$$$^{\text{∗}}$$$.

Cocoly is asked to partition the array $$$a$$$ into several (possibly, $$$1$$$ or $$$n$$$) non-empty continuous subsegments$$$^{\text{†}}$$$, such that: for each of the subsegments, the set containing all the elements in it is stable.

Master wants Cocoly to partition $$$a$$$ in at least two different$$$^{\text{‡}}$$$ ways. You have to help him determine whether it is possible.

Input format:
Each test contains multiple test cases. The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 200$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 200$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — the elements in the array $$$a$$$.

Output format:
For each test case, print $$$\texttt{YES}$$$ if there are at least two ways to partition $$$a$$$, and $$$\texttt{NO}$$$ otherwise.

You can output the answer in any case (upper or lower). For example, the strings $$$\texttt{yEs}$$$, $$$\texttt{yes}$$$, $$$\texttt{Yes}$$$, and $$$\texttt{YES}$$$ will be recognized as positive responses.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, here are two possible partitions:

- $$$[2, 3], [5, 7]$$$, since   $$$[2, 3]$$$ is stable because sticks of lengths $$$(2, 2, 2), (2, 2, 3), (2, 3, 3), (3, 3, 3)$$$ respectively can all form non-degenerate triangles.  $$$[5, 7]$$$ is stable because sticks of lengths $$$(5, 5, 5), (5, 5, 7), (5, 7, 7), (7, 7, 7)$$$ respectively can all form non-degenerate triangles.
- and $$$[2], [3, 5], [7]$$$, since   $$$[2]$$$ is stable because sticks of lengths $$$(2, 2, 2)$$$ respectively can form a non-degenerate triangle.  $$$[3, 5]$$$ is stable because sticks of lengths $$$(3, 3, 3), (3, 3, 5), (3, 5, 5), (5, 5, 5)$$$ respectively can all form non-degenerate triangles.  $$$[7]$$$ is stable because sticks of lengths $$$(7, 7, 7)$$$ respectively can form a non-degenerate triangle.

Note that some other partitions also satisfy the constraints, such as $$$[2], [3], [5], [7]$$$ and $$$[2], [3], [5, 7]$$$.

In the second test case, Cocoly can only partition each element as a single subsegment, resulting in $$$[115], [9], [2], [28]$$$. Since we only have one possible partition, the answer is $$$\texttt{NO}$$$.

In the third test case, please note that the partition $$$[8, 4], [1], [6], [2]$$$ does not satisfy the constraints, because $$$\{8, 4\}$$$ is not a stable set: sticks of lengths $$$4$$$, $$$4$$$, and $$$8$$$ cannot form a non-degenerate triangle.

Example input:
5
4
2 3 5 7
4
115 9 2 28
5
8 4 1 6 2
6
1 5 4 1 4 7
2
100000 100000

Example output:
YES
NO
NO
YES
YES

Editorial:
Note that: we always have a partition like $$$[a_1], [a_2], \dots, [a_n]$$$ since $$$(x, x, x)$$$ always form a non-degenerate (equilateral) triangle.
We focus on the second partition scheme in which not all continuous subsegments have a length of $$$1$$$. In fact, one can also note that if a set $$$S$$$ is stable then for all $$$T \subsetneq S$$$ ($$$T \neq \varnothing$$$), $$$T$$$ is also stable.
• Short proof: If $$$\exists u, v, w \in T$$$ such that $$$(u, v, w)$$$ does not form a non-degenerate triangle, therefore $$$u, v, w \in S$$$ so $$$S$$$ is not stable. Contradiction!
Therefore, if such a partition exists, it can always be boiled down into a continuous subsegment of length $$$2$$$ and other continuous subsegments of length $$$1$$$, and the partition remains valid. So we should output $$$\texttt{NO}$$$ if and only if for all $$$1 \leq i < n$$$, $$$2\min(a_i, a_{i+1}) \leq \max(a_i, a_{i+1})$$$.