Igor Perić

C. LIS or Reverse LIS?

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

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.

Input

The input consists of multiple test cases. The first line contains a single integer t (1≤t≤10^4)  — 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⋅10^5)  — the length of array a.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤10^9)  — the elements of the array a.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.

Output

For each test case, output a single integer  — the maximum possible beauty of a after rearranging its elements arbitrarily.

Example input

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

Example output

1
3
2

Note

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.

Solution

The key observation is LIS(a) = LDS(a’). We don’t have to reverse the array or traverse it from the other side, we just need to know that longest increasing and longest decreasing sub-sequence should have lengths as close to each other, so the min(LIS(a), LIS(a’)) is maximized.

By constructing a frequency table we can greedily construct the solution for LIS(a) by picking all of the values in the increasing order, and then construct the LDS(a) by picking all of the values that appear more than once (since we already used them once for LIS) in the decreasing order. Having a number appear more than 2 times doesn’t matter since we can inject it so it doesn’t have any effect on the resulting LIS and LDS.

Now, the constructed LIS and LDS have dis-balanced lengths – we constructed the LIS first so it will be longer than LDS. In order to fix that we should balance it using the elements which appear only once. In ideal case, we should use half of them for LIS and the other half for LDS. This means that the solution is multiple + single / 2.

The last observation is that one of these elements can be used twice when counting the lengths of LIS and LDS, since it will be a common element on which LIS stops and LDS starts. To account for that, we modify our final solution to be multiple + (single + 1) / 2

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main(){
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        map<unsigned long long, long long> f;
        unsigned long long k;
        for (int i=0;i<n;i++) {
            cin >> k;
            f[k] = f[k] + 1;
        }

        int single = 0, multiple = 0;
        for (auto it=f.begin();it!=f.end();it++) {
            if (it->second > 1) multiple++;
            else single++;
        }
        cout << multiple + (single + 1) / 2 << endl;
    }

    return 0;
}