你得到一个长度为 $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$ 之和。

1. （3 分）：$n = 4$；
2. （4 分）：$T = 1$, $n \le 7$；
3. （7 分）：$T = 1$, $n \le 15$；
4. （5 分）：如果存在某个满足条件的排列，那么一定存在一个满足条件的排列使得 $b_1 \ge b_2$ 且 $b_2 \le b_3$；
5. （17 分）：$S \le 50$；
6. （10 分）：$S \le 400$；
7. （13 分）：$S \le 2000$；
8. （9 分）：$S \le 8000$；
9. （18 分）：对于所有 $1 \le i \le n$，$a_i \le 10^6$；
10. （14 分）：无额外限制。