题目描述

题目译自 Ukrainian Olympiads in Informatics 2025 Stage 4 Day1 T3. Випуклий масив

给定一个长度为 $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$ 之和。详细子任务附加限制及分值如下表所示：