rt，好像被卡常了

// Date: 15/12/2024
#include <bits/stdc++.h>
// #define int long long
#define eb emplace_back
#define pb push_back
using namespace std;
const int N = 500100;

vector<int> to[N];
int a[N], bel[N], b[N], res[N];
signed main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) b[i] = a[i];
    sort(b + 1, b + n + 1);
    int m = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    for (int i = 1; i <= n; ++i) to[a[i]].eb(i);
    int ok = 1;
    for (int i = 1; i <= m; ++i)
        if (to[i].size() > 10) {ok = 0; break;}
    if (ok) {
        for (int i = 1; i <= m; ++i) {
            vector<int> v = {1};
            for (int j = 0; j < to[i].size(); ++j)
                for (int jj = j + 1; jj < to[i].size(); ++jj)
                    v.eb(to[i][jj] - to[i][j]);
            sort(v.begin(), v.end());
            v.erase(unique(v.begin(), v.end()), v.end());
            v.eb(n + 1);
            for (int id = 0; id < v.size() - 1; ++id) {
                int nu = v[id], un = v[id + 1];
                int idx = to[i].size(), las = 1;
                int pos = 1, cnt = 0;
                while (pos <= idx) {
                    if (pos == idx) {++cnt; break;}
                    int l = pos, r = idx, best = -1;
                    while (l <= r) {
                        int mid = l + r >> 1;
                        if (to[i][mid - 1] - to[i][pos - 1] <= nu) best = mid, l = mid + 1;
                        else r = mid - 1;
                    }
                    ++cnt;
                    pos = best + 1;
                }
                res[nu] += cnt, res[un] -= cnt;
            }
        }
        for (int i = 1; i <= n; ++i) res[i] += res[i - 1];
        for (int i = 1; i <= n; ++i) cout << res[i] << '\n';
        return 0;
    }
    for (int i = 1; i <= m; ++i) {
        if (to[i].size() > 49) {
            for (int nu = 1; nu <= n; ++nu) {
                int cnt = 0;
                int idx = to[i].size(), las = 1;
                int pos = 1;
                while (pos <= idx) {
                    if (pos == idx) {++cnt; break;}
                    int l = pos, r = idx, best = -1;
                    while (l <= r) {
                        int mid = l + r >> 1;
                        if (to[i][mid - 1] - to[i][pos - 1] <= nu) best = mid, l = mid + 1;
                        else r = mid - 1;
                    }
                    ++cnt;
                    pos = best + 1;
                }
                res[nu] += cnt, res[nu + 1] -= cnt;
            }
        } else {
            vector<int> v = {1};
            for (int j = 0; j < to[i].size(); ++j)
                for (int jj = j + 1; jj < to[i].size(); ++jj)
                    v.eb(to[i][jj] - to[i][j]);
            sort(v.begin(), v.end());
            v.erase(unique(v.begin(), v.end()), v.end());
            v.eb(n + 1);
            for (int id = 0; id < v.size() - 1; ++id) {
                int nu = v[id], un = v[id + 1];
                int idx = to[i].size(), las = 1;
                int pos = 1, cnt = 0;
                while (pos <= idx) {
                    if (pos == idx) {++cnt; break;}
                    int l = pos, r = idx, best = -1;
                    while (l <= r) {
                        int mid = l + r >> 1;
                        if (to[i][mid - 1] - to[i][pos - 1] <= nu) best = mid, l = mid + 1;
                        else r = mid - 1;
                    }
                    ++cnt;
                    pos = best + 1;
                }
                res[nu] += cnt, res[un] -= cnt;
            }
        }
    }
    for (int i = 1; i <= n; ++i) res[i] += res[i - 1];
    for (int i = 1; i <= n; ++i) cout << res[i] << '\n';
    return 0;
}