D. Epic Transformation

Problem - 1506D - CodeforcesD. Epic Transformation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa of length nn consisting of integers. You can apply the following operation, consisting of several steps, on the array aa zero or more times:

• you select two different numbers in the array aiai and ajaj;
• you remove ii-th and jj-th elements from the array.

For example, if n=6n=6 and a=[1,6,1,1,4,4]a=[1,6,1,1,4,4], then you can perform the following sequence of operations:

• select i=1,j=5i=1,j=5. The array aa becomes equal to [6,1,1,4][6,1,1,4];
• select i=1,j=2i=1,j=2. The array aa becomes equal to [1,4][1,4].

What can be the minimum size of the array after applying some sequence of operations to it?

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104). Then tt test cases follow.

The first line of each test case contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105) is length of the array aa.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).

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

Output

For each test case, output the minimum possible size of the array after applying some sequence of operations to it.

Example

input

Copy

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

output

Copy

0
0
2
1
0
=======================================================================================

很老的贪心，只需要每次取出来最大的两个数字就行了，使用优先队列和map即可

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
 
typedef long long int  ll;
 
priority_queue<int>q;
map<int,int>mp;
int main()
{
 
    int t;
 
    cin>>t;
 
    while(t--)
    {
        int n;
 
        cin>>n;
 
        mp.clear();
 
        while(!q.empty())
            q.pop();
 
        for(int i=1;i<=n;i++)
        {
            int x;
 
            cin>>x;
 
            mp[x]++;
        }
 
        for(auto it:mp)
        {
            q.push(it.second);
        }
 
 
        while(q.size()>=2)
        {
            int now=q.top();
 
            q.pop();
 
            int now1=q.top();
 
            q.pop();
 
            now--;
 
            now1--;
 
            if(now)
                q.push(now);
 
            if(now1)
                q.push(now1);
        }
 
        if(q.size()==0)
        {
            cout<<0<
        }
        else
        {
            cout<top()<
 
        }
    }
 
 
 
 
 
    return 0;
}