#CW48. 凸序列(convex)

凸序列(convex)

题目描述

小 W 手中有一个长度为 nn 的整数多重集合。他想把这些数排成序列 b1,b2,…,bnb_1,b_2,\dots,b_n,使每个内部位置都满足

bi−1+bi+1≥2bi(2≤i≤n−1).b_{i-1}+b_{i+1}\ge 2b_i\qquad(2\le i\le n-1).

请判断是否存在这样的排列。

输入格式

第一行一个整数 TT。接下来描述 TT 组数据。每组数据第一行一个整数 nn,第二行给出 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n。

输出格式

对于每组数据,若存在满足条件的排列,输出 YES,否则输出 NO。

样例 1 输入

3
4
0 3 4 6
4
5 4 1 4
6
1 2 3 4 5 6

样例 1 输出

YES
NO
YES

样例 2 输入

2
4
0 1 1 1
8
0 2 4 6 8 10 12 14

样例 2 输出

NO
YES

样例 3 输入

2
15
0 1 1 1 2 3 4 5 6 7 8 9 10 11 12
15
0 5 10 15 20 25 30 35 40 45 50 55 60 65 70

样例 3 输出

NO
YES

样例 4 输入

2
7
1 1 1 1 1 1 1
7
3 6 9 12 15 18 21

样例 4 输出

YES
YES

样例 5 输入

2
10
0 1 1 1 1 2 3 4 5 6
10
0 10 20 30 40 50 60 70 80 90

样例 5 输出

NO
YES

数据范围

所有数据满足 1≤T≤1051\le T\le 10^5、3≤n≤3×1053\le n\le 3\times 10^5、0≤ai≤1090\le a_i\le 10^9,且单个输入文件中所有 nn 的总和不超过 3×1053\times 10^5。

本题采用子任务捆绑计分。每个正式输入文件包含多组数据。

子任务 分值 测试点 附加条件
1 3 1∼21\sim 2 n=4n=4
2 4 3∼43\sim 4 每组数据满足 n≤7n\le 7
3 7 5∼65\sim 6 每组数据满足 n≤15n\le 15
4 5 7∼87\sim 8 若存在合法排列,则存在满足 b1≥b2≤b3b_1\ge b_2\le b_3 的合法排列
5 17 9∼109\sim 10 所有数据的 nn 之和不超过 5050
6 10 11∼1211\sim 12 所有数据的 nn 之和不超过 400400
7 13 13∼1413\sim 14 所有数据的 nn 之和不超过 20002000
8 9 15∼1615\sim 16 所有数据的 nn 之和不超过 80008000
9 18 17∼1817\sim 18 所有 ai≤106a_i\le 10^6
10 14 19∼2019\sim 20 无额外限制