你得到一个长度为 $n$ 的整数数组 $a$。
判断是否存在一个它的排列 $b$，使得对于每个 $2\leq i \leq n-1$，都有 $b_{i-1} + b_{i+1} \ge 2\cdot b_i$ 成立。
本题中，每个测试包含若干组输入数据。你需要对每组数据独立地解决问题。
输入
第一行包含一个整数 $T$ $(1\le T\le 10^5)$~--- 输入数据组数。接下来是每组输入数据的描述。
每组输入数据的第一行是一个整数 $n$ $(3\le n\le 3\cdot 10^5)$~--- 数组 $a$ 的长度。
每组输入数据的第二行是 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(0\le a_i\le 10^9)$~--- 数组 $a$ 的元素。
保证单个测试中所有输入数据组的 $n$ 之和不超过 $3\cdot 10^5$。
输出
对于每组输入数据，输出一行 YES，如果存在满足要求的排列；否则输出 NO。
示例
输入
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
输出
YES NO NO YES YES NO YES YES YES NO
说明
在第一个例子中的第一组输入数据中，数组 $[0, 3, 4, 6]\$ 满足条件的排列是 $[4, 0, 3, 6]$ 和 $[6, 3, 0, 4]$。
评分
设 $S$ 是单个测试中所有输入数据组的 $n$ 之和。
- （3 分）：$n = 4$；
- （4 分）：$T = 1$, $n \le 7$；
- （7 分）：$T = 1$, $n \le 15$；
- （5 分）：如果存在某个满足条件的排列，那么一定存在一个满足条件的排列使得 $b_1 \ge b_2$ 且 $b_2 \le b_3$；
- （17 分）：$S \le 50$；
- （10 分）：$S \le 400$；
- （13 分）：$S \le 2000$；
- （9 分）：$S \le 8000$；
- （18 分）：对于所有 $1 \le i \le n$，$a_i \le 10^6$；
- （14 分）：无额外限制。