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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;


int tab[300001];

int v[300001];

map<int, int> M;

int main()
{
  
  int n;
  scanf("%d", &n);
  
  for (int i = 0; i < n; i++)
  {
    scanf("%d", tab + i);
    M[tab[i]]++;
  }
  
  int c = 0;
  
  for (auto it : M)
  {
    v[c] = it.second;
    c++;
  }
  
  sort(v, v + c);  

  for (int i = 0; i < n; i++)
  {
    long long s = 0;
    int pop = 0;

    auto it = lower_bound(v, v + c, i + 1);
    int idx = it - v;
    pop = idx;

    int a = v[idx];
    a /= (i + 1);
    a = a * (i + 1);
    
    it = upper_bound(v + idx, v + c, a + i);
    
    idx = it - v;

    s += 1LL * (idx - pop) * a;
    
    for (int j = idx; j < c;)
    {
      pop = idx;
      a = v[j] / (i + 1);
      a = a * (i + 1);
      auto it = upper_bound(v + idx, v + c, a + i);
      idx = it - v;
      j = idx;
      s += 1LL * (idx - pop ) * a;
    }
    
    printf("%lld ", s);
  }
  return 0;  
}