C. LIS or Reverse LIS?

Problem - 1682C - Codeforces

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 aa of nn positive integers.

Let LIS(a)LIS(a) denote the length of longest strictly increasing subsequence of aa. For example,

• LIS([2,1–,1,3–])LIS([2,1_,1,3_]) = 22.
• LIS([3–,5–,10–––,20–––])LIS([3_,5_,10_,20_]) = 44.
• LIS([3,1–,2–,4–])LIS([3,1_,2_,4_]) = 33.

We define array a′a′ as the array obtained after reversing the array aa i.e. a′=[an,an−1,…,a1]a′=[an,an−1,…,a1].

The beauty of array aa is defined as min(LIS(a),LIS(a′))min(LIS(a),LIS(a′)).

Your task is to determine the maximum possible beauty of the array aa if you can rearrange the array aa arbitrarily.

Input

The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤104)(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 nn (1≤n≤2⋅105)(1≤n≤2⋅105)  — the length of array aa.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤109)(1≤ai≤109)  — the elements of the array aa.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.

Output

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

Example

input

Copy

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

output

Copy

1
3
2

Note

In the first test case, aa = [6,6,6][6,6,6] and a′a′ = [6,6,6][6,6,6]. LIS(a)=LIS(a′)LIS(a)=LIS(a′) = 11. Hence the beauty is min(1,1)=1min(1,1)=1.

In the second test case, aa can be rearranged to [2,5,4,5,4,2][2,5,4,5,4,2]. Then a′a′ = [2,4,5,4,5,2][2,4,5,4,5,2]. LIS(a)=LIS(a′)=3LIS(a)=LIS(a′)=3. Hence the beauty is 33 and it can be shown that this is the maximum possible beauty.

In the third test case, aa can be rearranged to [1,2,3,2][1,2,3,2]. Then a′a′ = [2,3,2,1][2,3,2,1]. LIS(a)=3LIS(a)=3, LIS(a′)=2LIS(a′)=2. Hence the beauty is min(3,2)=2min(3,2)=2 and it can be shown that 22 is the maximum possible beauty.

========================================================================

要让最小值最大，也就是正反的LIS尽量差不多大，可以把最大的放在中间，然后大小递减依次排开，也可以把最小的放在中间，但这样一旦出现了大于等于3的元素，就会把我们一边给搞乱，所以直接统计小于等于2次的元素，除以2上取整即可。因为最终贡献每个数最多贡献两次。

# include<bits/stdc++.h>
using namespace std;
# define mod 1000000009

typedef long long int ll;
map<int,int>mp;
int main ()
{



    int t;

    cin>>t;

    while(t--)
    {
        int n;
        cin>>n;
        mp.clear();
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            mp[x]++;

            if(mp[x]<=2)
                cnt++;
        }

        int ans=cnt/2;
        if(cnt%2)
            ans++;
        cout<<ans<<'\n';

    }


    return 0;
}