2025_1C. Convex Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of integers $$$a$$$ of length $$$n$$$.

Determine whether there exists a permutation of its elements $$$b$$$ such that for every $$$2\leq i \leq n-1$$$, the condition $$$b_{i-1} + b_{i+1} \ge 2\cdot b_i$$$ holds.

In this problem, each test contains several sets of input data. You need to solve the problem independently for each such set.

Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 10^5)$$$ — the number of sets of input data. The description of the input data sets follows.

In the first line of each input data set, there is a single integer $$$n$$$ $$$(3\le n\le 3\cdot 10^5)$$$ — the length of the array $$$a$$$.

In the second line of each input data set, there are $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0\le a_i\le 10^9)$$$ — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ across all input data sets of a single test does not exceed $$$3\cdot 10^5$$$.

Output

For each set of input data, output on a separate line "YES", if the desired permutation exists, and "NO" otherwise.

Scoring

Let $$$S$$$ be the sum $$$n$$$ over all input data sets of one test.

  1. ($$$3$$$ points): $$$n = 4$$$;
  2. ($$$4$$$ points): $$$T = 1$$$, $$$n \le 7$$$;
  3. ($$$7$$$ points): $$$T = 1$$$, $$$n \le 15$$$;
  4. ($$$5$$$ points): if some desired permutation exists, then there exists such a desired permutation for which $$$b_1 \ge b_2$$$ and $$$b_2 \le b_3$$$;
  5. ($$$17$$$ points): $$$S \le 50$$$;
  6. ($$$10$$$ points): $$$S \le 400$$$;
  7. ($$$13$$$ points): $$$S \le 2000$$$;
  8. ($$$9$$$ points): $$$S \le 8000$$$;
  9. ($$$18$$$ points): $$$a_i \le 10^6$$$ for $$$1 \le i \le n$$$;
  10. ($$$14$$$ points): without additional restrictions.
Example
Input
10
4
0 3 4 6
4
5 4 1 4
8
1 4 4 8 6 10 10 4
7
2 1 5 1 9 4 6
6
7 1 6 10 2 3
7
6 6 10 2 5 3 8
4
9 9 1 5
4
8 4 3 4
7
1 2 1 6 4 2 9
7
3 9 7 5 9 10 10
Output
YES
NO
NO
YES
YES
NO
YES
YES
YES
NO
Note

In the first set of input data from the first example, the permutations of the array $$$[0, 3, 4, 6]$$$ that satisfy the described condition are $$$[4, 0, 3, 6]$$$ and $$$[6, 3, 0, 4]$$$.