#1417. [UOI 2025] Convex Array

[UOI 2025] Convex Array

题目描述

给定一个长度为 nn 的整数数组 aa。

判断是否存在一种元素排列 bb,使得对于每个 2≤i≤n−12 \leq i \leq n-1,都满足条件 bi−1+bi+1≥2⋅bib_{i-1} + b_{i+1} \geq 2 \cdot b_i。

本题中,每个测试点包含多组输入数据。你需要对每组数据独立求解。

输入格式

第一行包含一个整数 TT (1≤T≤105)(1 \le T \le 10^5) —— 输入数据的组数。接下来是各组数据的描述。

每组数据的第一行包含一个整数 nn (3≤n≤3⋅105)(3 \le n \le 3 \cdot 10^5) —— 数组 aa 的长度。

每组数据的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n (0≤ai≤109)(0 \le a_i \le 10^9) —— 数组 aa 的元素。

保证单个测试点中所有输入数据的 nn 之和不超过 3⋅1053 \cdot 10^5。

输出格式

对于每组输入数据,如果存在满足条件的排列,输出一行 YES\tt{YES},否则输出 NO\tt{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

题目来源:洛谷 P12546