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.

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

Notes

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]$.

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.