CF786C

// Problem: C. Till I Collapse
// Contest: Codeforces - Codeforces Round 406 (Div. 1)
// URL: https://codeforces.com/contest/786/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

int calc(const vi &v, int k)
{
    int ret = 0;
    set<int> sz;
    for (auto x : v) {
        if (sz.size() == k && sz.count(x) == 0) {
            sz.clear();
            ++ret;
        }
        sz.insert(x);
    }
    if (sz.size())
        ++ret;
    return ret;
}

int calc1(const vi &v, int k)
{
    vi time(1e5 + 3);
    int clock = 1, left = k, ret = 0;
    for (auto x : v) {
        if (time[x] == clock)
            continue;
        if (left == 0) {
            left = k;
            ++clock;
            ++ret;
        }
        time[x] = clock;
        --left;
    }
    return ret + (left != k);
}

void search(vi &ans, const vi &v, int l, int r)
{
    if (ans[l] == -1)
        ans[l] = calc1(v, l + 1);
    if (ans[r - 1] == -1)
        ans[r - 1] = calc1(v, r);
    if (ans[l] == ans[r - 1]) {
        for (int i = l + 1; i < r - 1; ++i)
            ans[i] = ans[l];
        return;
    }
    if (l + 1 == r)
        return;
    int m = (l + r) / 2;
    search(ans, v, l, m), search(ans, v, m, r);
}

int main(int argc, char **argv)
{
    int n;
    cin >> n;
    vi a(n);
    for (auto &x : a)
        cin >> x;
    a.erase(std::unique(a.begin(), a.end()), a.end());
    vi ans(n, -1);

    search(ans, a, 0, n);
    for (auto x : ans)
        cout << x << ' ';
    cout << endl;
    return 0;
};