#212603. [UOI 2025] Convex Array

You are given an array of integers of length .

Determine whether there exists a permutation of its elements such that for every , the condition holds.

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

The first line contains a single integer --- 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 --- the length of the array .

In the second line of each input data set, there are integers --- the elements of the array .

It is guaranteed that the sum of across all input data sets of a single test does not exceed .

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

样例输入 1

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

样例输出 1

YES
NO
NO
YES
YES
NO
YES
YES
YES
NO

In the first set of input data from the first example, the permutations of the array that satisfy the described condition are and .

Scoring

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

• ( points): ;
• ( points): , ;
• ( points): , ;
• ( points): if some desired permutation exists, then there exists such a desired permutation for which and ;
• ( points): ;
• ( points): ;
• ( points): ;
• ( points): ;
• ( points): for ;
• ( points): without additional restrictions.