1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    map<int, int> M;
    for(int i = 0; i < n; i++) {
        int x; cin >> x;
        M[x]++;
    }
    vector<int> ans(n + 1, 0);
    vector<queue<int>> q(n + 1, queue<int>());
    for(auto x : M) {
        q[min(n, x.second)].push(x.second);
        ans[min(n, x.second)] += x.second/min(n, x.second);
    }
    for(int i = n; i > 1; i--) {
        while(!q[i].empty()) {
            int x = q[i].front();
            q[i].pop();
            if(i > sqrt(x)) { // next value might be further away than 1
                int val = x / i;
                int new_i = x / (val + 1);
                q[new_i].push(x);
                ans[new_i] += (x / new_i) - val;
                //cout << x << " " << i << " " << new_i << " case : 1\n";
            } else { // next value might be bigger than 1
                
                int val = x / i;
                int new_val = x / (i - 1);
                q[i - 1].push(x);
                ans[i - 1] += (new_val - val);
                //cout << x << " " << i << " " << val << " " << new_val << " case : 2\n";
            }
        }
    }
    for(int i = n - 1; i >= 1; i--) {
        ans[i] += ans[i + 1];
    }
    for(int i = 1; i <= n; i++) {
        cout << ans[i] * i << " ";
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}