P12546 [UOI 2025] Convex Array

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.

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

For each set of input data, output on a separate line $\tt{YES}$, if the desired permutation exists, and $\tt{NO}$ otherwise.

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. - ($3$ points): $n = 4$; - ($4$ points): $T = 1$, $n \le 7$; - ($7$ points): $T = 1$, $n \le 15$; - ($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$; - ($17$ points): $S \le 50$; - ($10$ points): $S \le 400$; - ($13$ points): $S \le 2000$; - ($9$ points): $S \le 8000$; - ($18$ points): $a_i \le 10^6$ for $1 \le i \le n$; - ($14$ points): without additional restrictions.