题面翻译
设一个长为 n 的整数序列 a 是 {a1,a2,a3,⋯,an},那么 a′ 表示 {an,an−1,an−2,⋯,a1},LIS(a) 表示 a 的最长严格上升子序列的长度。
现在给定 a 数组,请你将 a 数组重新排列,使得重排后的 min(LIS(a),LIS(a′)) 最大。
输入 t 组数据,每组数据先输入 n ,然后输入 n 个整数,所有 n 之和不超过 2×105。
输出 t 行,每行一组数据的答案,按输入顺序输出。
题目描述
You are given an array a of n positive integers.
Let LIS(a) denote the length of longest strictly increasing subsequence of a . For example,
- LIS([2,1,1,3]) = 2 .
- LIS([3,5,10,20]) = 4 .
- LIS([3,1,2,4]) = 3 .
We define array a′ as the array obtained after reversing the array a i.e. a′=[an,an−1,…,a1] .
The beauty of array a is defined as min(LIS(a),LIS(a′)) .
Your task is to determine the maximum possible beauty of the array a if you can rearrange the array a arbitrarily.
输入格式
The input consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. Description of the test cases follows.
The first line of each test case contains a single integer n (1≤n≤2⋅105) — the length of array a .
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109) — the elements of the array a .
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 .
输出格式
For each test case, output a single integer — the maximum possible beauty of a after rearranging its elements arbitrarily.
样例 #1
样例输入 #1
3
3
6 6 6
6
2 5 4 5 2 4
4
1 3 2 2
样例输出 #1
1
3
2
提示
In the first test case, a = [6,6,6] and a′ = [6,6,6] . LIS(a)=LIS(a′) = 1 . Hence the beauty is min(1,1)=1 .
In the second test case, a can be rearranged to [2,5,4,5,4,2] . Then a′ = [2,4,5,4,5,2] . LIS(a)=LIS(a′)=3 . Hence the beauty is 3 and it can be shown that this is the maximum possible beauty.
In the third test case, a can be rearranged to [1,2,3,2] . Then a′ = [2,3,2,1] . LIS(a)=3 , LIS(a′)=2 . Hence the beauty is min(3,2)=2 and it can be shown that 2 is the maximum possible beauty.