题目描述

给定一个长度为 $n$ 的整数数组 $a$。

判断是否存在一种元素排列 $b$，使得对于每个 $2 \leq i \leq n-1$，都满足条件 $b_{i-1} + b_{i+1} \geq 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$。

输出格式

对于每组输入数据，如果存在满足条件的排列，输出一行 $\tt{YES}$，否则输出 $\tt{NO}$。

输入输出样例 #1

输入 #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

说明/提示

在第一个样例的第一组输入数据中，数组 $[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$ 分）：无额外限制。