Algorithm

E. Thematic Contests
time limit per test
1 second
memory limit per test
256 megabytes
problem link- https://codeforces.com/contest/1077/problem/E
input
standard input
output
standard output

Polycarp has prepared n� competitive programming problems. The topic of the i�-th problem is ai��, 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⋅1051≤�≤2⋅105) — the number of problems Polycarp has prepared.

The second line of the input contains n� integers a1,a2,…,an�1,�2,…,�� (1≤ai≤1091≤��≤109) where ai�� 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
Copy
18
2 1 2 10 2 10 10 2 2 1 10 10 10 10 1 1 10 10
output
Copy
14
input
Copy
10
6 6 6 3 6 1000000000 3 3 6 6
output
Copy
9
input
Copy
3
1337 1337 1337
output
Copy
3
Note

In the first example the optimal sequence of contests is: 22 problems of the topic 11, 44 problems of the topic 22, 88 problems of the topic 1010.

In the second example the optimal sequence of contests is: 33 problems of the topic 33, 66 problems of the topic 66.

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

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 2e5 + 1;
int n, a[N], fr[N];
vector<int> all;

int main() {
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d", a + i), all.push_back(a[i]);

  sort(all.begin(), all.end());
  all.resize(unique(all.begin(), all.end()) - all.begin());
  for(int i = 0; i < n; ++i)
    a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin(),
    ++fr[a[i]];
  all.clear();

  for(int i = 0; i < N; ++i)
    if(fr[i] != 0)
      all.push_back(fr[i]);
  sort(all.begin(), all.end());

  int res = 0, tmp, idx, cur;
  for(int i = 1; i <= all.back(); ++i) {
    tmp = 0, idx = -1, cur = i;
    while(true) {
      idx = lower_bound(all.begin() + idx + 1, all.end(), cur) - all.begin();
      if(idx == all.size())
        break;
      tmp += cur;
      cur += cur;
    }
    res = max(res, tmp);
  }
  printf("%d\n", res);

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
18
2 1 2 10 2 10 10 2 2 1 10 10 10 10 1 1 10 10

Output

x
–
+
cmd
14
Advertisements

Demonstration

Codeforces Solution-E. Thematic Contests-Solution in C, C++, Java, Python ,Thematic Contests,Codeforces Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+