Convex Array#11812
Sign in

Convex Array

1 second
256 megabytes
Very hard

You are given an array of integers of length .

Determine whether there exists a permutation of its elements 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 (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 (3\le n\le 3\cdot 10^5) — the length of the array .

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

It is guaranteed that the sum of 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.

Examples

Example 1

Loading
Loading

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

Scoring

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

  1. ( points): n = 4;

  2. ( points): T = 1, n \le 7;

  3. ( points): T = 1, n \le 15;

  4. ( 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. ( points): S \le 50;

  6. ( points): S \le 400;

  7. ( points): S \le 2000;

  8. ( points): S \le 8000;

  9. ( points): a_i \le 10^6 for 1 \le i \le n;

  10. ( points): without additional restrictions.