Thematic Contests

https://codeforces.com/contest/1077/problem/E

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp has prepared nn competitive programming problems. The topic of the ii-th problem is aiai, and some problems' topics may coincide.

Polycarp has to host several thematic contests. All problems in each contest should have the same topic, and all contests should have pairwise distinct topics. He may not use all the problems. It is possible that there are no contests for some topics.

Polycarp wants to host competitions on consecutive days, one contest per day. Polycarp wants to host a set of contests in such a way that:

• number of problems in each contest is exactly twice as much as in the previous contest (one day ago), the first contest can contain arbitrary number of problems;
• the total number of problems in all the contests should be maximized.

Your task is to calculate the maximum number of problems in the set of thematic contests. Note, that you should not maximize the number of contests.

Input

The first line of the input contains one integer n (1≤n≤2⋅105) — the number of problems Polycarp has prepared.

The second line of the input contains nn integers a1,a2,…,an (1≤ai≤109) where aiai is the topic of the i-th problem.

Output

Print one integer — the maximum number of problems in the set of thematic contests.

Examples

input

18
2 1 2 10 2 10 10 2 2 1 10 10 10 10 1 1 10 10

output

14

input

10
6 6 6 3 6 1000000000 3 3 6 6

output

9

input

3
1337 1337 1337

output

3

Note

In the first example the optimal sequence of contests is: 2 problems of the topic 1, 4 problems of the topic 2, 8 problems of the topic 10.

In the second example the optimal sequence of contests is: 3 problems of the topic 3, 6 problems of the topic 6.

In the third example you can take all the problems with the topic 1337 (the number of such problems is 3 so the answer is 3) and host a single contest.

C++版本一

二分

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;
typedef long long ll;
const int N=200000+100;
int t,n,k;
int a[N],X[N];
bool BS(int x){
    int l=1;
    int r=n;
    int mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(X[mid]<x)
            l=mid+1;
        else{
            r=mid-1;
            return 1;
        }
    }
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    X[1]=1;
    int cnt=1;
    for(int i=2;i<=n;i++){
        if(a[i-1]!=a[i])
            X[++cnt]=1;
        else
            X[cnt]++;
    }
    sort(X+1,X+cnt+1);
    int ans=1,flag=1,d=X[1];
    for(int i=1;i<=cnt;i++){
        //cout << "X="<<X[i] << endl;
        for(int j=1;j<=X[i];j++){
            flag=1;
            int tmp=j;
            int find=lower_bound(X+i+1,X+cnt+1,2*tmp)-X;;
            while(find<=cnt){
                flag++;
                //cout << "find"<<find<<"tmp"<<tmp << endl;
                tmp*=2;
                find=lower_bound(X+find+1,X+cnt+1,2*tmp)-X;

            }
            int temp=j*(pow(2,flag)-1);
            ans=max(ans,temp);
        }
    }
    cout << ans << endl;
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

The first thing: we don't need the problems, we need their counts. So let's calculate for each topic the number of problems with this topic and sort them in non-decreasing order. The counting can be done with std::map or another one sorting.

The second thing: the answer is not exceed n (very obviously). So let's iterate over the number of problems in maximum by the number of problems thematic contest. Now we have to calculate the maximum number of problems we can take in the set of thematic contests. Let's do it greedily.

The number of contests in the set don't exceed log⁡n. Let the number of problems in the current contest be cur (at the beginning of iteration the current contest is the maximum by the number of problems). Let's take the topic with the maximum number of problems for this contest. If we cannot do it, stop the iteration. Otherwise we can (maybe) continue the iteration. If cur is even then divide it by 2 and continue with the rest of topics, otherwise stop the iteration. Which topic we have to choose for the second one contest? The answer is: the topic with the maximum number of problems (which isn't chosen already). So let's carry the pointer pos (initially it is at the end of the array of counts) and decrease it when we add another one contest to our set. All calculations inside the iteration are very obviously.

Let's notice that one iteration spends at most lognlog⁡n operations. So overall complexity of the solution is O(nlog⁡n).

The last question is: why can we take the maximum by the number of problems topic each time? Suppose we have two contests with numbers of problems x and y, correspondingly. Let's consider the case when x<y. Let the number of problems of the first contest topic be cntx and the number of problems of the second contest topic be cnty. The case cntx≤cnty don't break our assumptions. The only case which can break our assumptions is cntx>cnty. So if it is then we can swap these topics (because x<y and cntx>cnty) and all will be okay. So this greedy approach works.

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	map<int, int> cnt;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		++cnt[x];
	}
	
	vector<int> cnts;
	for (auto it : cnt) {
		cnts.push_back(it.second);
	}
	sort(cnts.begin(), cnts.end());
	
	int ans = 0;
	for (int i = 1; i <= cnts.back(); ++i) {
		int pos = int(cnts.size()) - 1;
		int cur = i;
		int res = cur;
		while (cur % 2 == 0 && pos > 0) {
			cur /= 2;
			--pos;
			if (cnts[pos] < cur) break;
			res += cur;
		}
		ans = max(ans, res);
	}
	cout << ans << endl;
	
	return 0;
}