Answer to Question #155555 in C++ for Abu Ubayda

Question

Suppose you are a billionaire businessman and have recently bought a football club. You have also bought many star players from over the world. But for some reasons, you have not selected a coach yet to run your football club. One day, you had a thought, "Why don’t I coach my own team?!!" Now, you want to act upon this thought and want to coach your own team in your own style. You have n players in your team under your control and you have to compose exactly two teams of the same size (two teams because, you want to test each of the team’s strengths by playing them against each other) consisting of some subset of your players. Each player has his own skill in football and the i-th player’s skill is denoted by an integer ai . Naturally, different players can have the same skills.

Now, the match will be valid if

• The first team should consist of players with distinct skills (i.e. all skills in the first team are unique).
• The second team should consist of players with the same skills (i.e. all skills in the second team are equal).

Note that it is permissible that some player of the first team has the same skill as a player of the second team.

Consider some formation:

• [1,2,3], [4,4] is not a good pair of teams because sizes should be the same;
• [1,1,2], [3,3,3] is not a good pair of teams because the first team should not contain players with the same skills;
• [1,2,3], [3,4,4] is not a good pair of teams because the second team should contain players with the same skills;
• [1,2,3], [3,3,3] is a good pair of teams;
• [5], [6] is a good pair of teams.

Your task is to find the maximum possible size p for which it is possible to compose a valid pair of teams, where each team size is p. A player cannot be part of more than one team.

Input Format

The first line of the input contains one integer t (1≤t≤10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1≤n≤2⋅10^5) — the number of players. The second line of the test case contains n integers a1,a2,…,an (1≤ai≤n), where ai is the skill of the i-th player.

Constraints

t (1≤t≤10^4), n (1≤n≤2⋅10^5)

Output Format

For each test case, print the answer — the maximum possible size p for which it is possible to compose a valid pair of teams, where each team size is p.

Sample Input 0

4
7
4 2 4 1 4 3 4
5
2 1 5 4 3
1
1
4
1 1 1 3

Sample Output 0

3
1
0
2

Answer 1

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxx=2e5+100;
int a[maxx];
int vis[maxx];
int n;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) vis[i]=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),vis[a[i]]++;
        int _max=0;
        int _min=0;
        for(int i=1;i<=n;i++)
        {
            _max=max(_max,vis[i]);
            if(vis[i]!=0) _min++;
        }
        _min-=1;
        int ans=min(_min,_max);
        if(_max-ans>=2) ans++;
        cout<<ans<<endl;
    }
    return 0;
}