Rick and Morty want to find MR. PBH and they can't do it alone. So they need of Mr. Meeseeks. They Have generated n Mr. Meeseeks, standing in a line numbered from 1 to n. Each of them has his own color. i-th Mr. Meeseeks' color is ai. 

Rick and Morty are gathering their army and they want to divide Mr. Meeseeks into some squads. They don't want their squads to be too colorful, so each squad should have Mr. Meeseeks of at most k different colors. Also each squad should be a continuous subarray of Mr. Meeseeks in the line. Meaning that for each 1 ≤ i ≤ e ≤ j ≤ n, if Mr. Meeseeks number i and Mr. Meeseeks number j are in the same squad then Mr. Meeseeks number e should be in that same squad.

<image>

Also, each squad needs its own presidio, and building a presidio needs money, so they want the total number of squads to be minimized.

Rick and Morty haven't finalized the exact value of k, so in order to choose it, for each k between 1 and n (inclusive) need to know the minimum number of presidios needed.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 105) — number of Mr. Meeseeks.

The second line contains n integers a1, a2, ..., an separated by spaces (1 ≤ ai ≤ n) — colors of Mr. Meeseeks in order they standing in a line.

Output

In the first and only line of input print n integers separated by spaces. i-th integer should be the minimum number of presidios needed if the value of k is i.

Examples

Input

5
1 3 4 3 3


Output

4 2 1 1 1 


Input

8
1 5 7 8 1 7 6 1


Output

8 4 3 2 1 1 1 1 

Note

For the first sample testcase, some optimal ways of dividing army into squads for each k are:

  1. [1], [3], [4], [3, 3]
  2. [1], [3, 4, 3, 3]
  3. [1, 3, 4, 3, 3]
  4. [1, 3, 4, 3, 3]
  5. [1, 3, 4, 3, 3]



For the second testcase, some optimal ways of dividing army into squads for each k are:

  1. [1], [5], [7], [8], [1], [7], [6], [1]
  2. [1, 5], [7, 8], [1, 7], [6, 1]
  3. [1, 5, 7], [8], [1, 7, 6, 1]
  4. [1, 5, 7, 8], [1, 7, 6, 1]
  5. [1, 5, 7, 8, 1, 7, 6, 1]
  6. [1, 5, 7, 8, 1, 7, 6, 1]
  7. [1, 5, 7, 8, 1, 7, 6, 1]
  8. [1, 5, 7, 8, 1, 7, 6, 1]
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;
const double inf = 1e121;
const double eps = 1e-10;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randint(int l, int r) {
  int out = rng() % (r - l + 1) + l;
  return out >= l ? out : out + r - l + 1;
}
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ",";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ",";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + "," + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + "," + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + "," + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + "," + to_string(get<3>(p)) + ")";
}
template <typename A, typename B, typename C, typename D, typename E>
string to_string(tuple<A, B, C, D, E> p) {
  return "(" + to_string(get<0>(p)) + "," + to_string(get<1>(p)) + "," +
         to_string(get<2>(p)) + "," + to_string(get<3>(p)) + "," +
         to_string(get<4>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
const int INF = 0x3f3f3f3f;
template <typename T>
typename enable_if<!is_integral<T>::value, void>::type read(T& x) {
  cin >> x;
}
long long read() {
  char c;
  long long out = 0, f = 1;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
    ;
  if (c == '-') {
    f = -1;
    c = getchar();
  }
  for (; isdigit(c); c = getchar()) out = (out << 3) + (out << 1) + c - '0';
  return out * f;
}
template <typename T>
typename enable_if<is_integral<T>::value, T>::type read(T& x) {
  char c;
  T f = 1;
  x = 0;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
    ;
  if (c == '-') {
    f = -1;
    c = getchar();
  }
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
  return x *= f;
}
char read(char& x) {
  for (x = getchar(); isspace(x); x = getchar())
    ;
  return x;
}
double read(double& x) {
  scanf("%lf", &x);
  return x;
}
long double read(long double& x) {
  scanf("%Lf", &x);
  return x;
}
template <typename T>
typename enable_if<!is_integral<T>::value, void>::type write(const T& x) {
  cout << x;
}
template <typename T>
typename enable_if<is_integral<T>::value, void>::type write(const T& x) {
  if (x < 0) {
    putchar('-');
    write(-x);
    return;
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
void write(const char& x) { putchar(x); }
void write(const double& x) { printf("%.10lf", x); }
void write(const long double& x) { printf("%.10Lf", x); }
template <typename T, typename... Args>
void read(T& x, Args&... args) {
  read(x);
  read(args...);
}
template <
    typename OutputIt,
    typename = typename enable_if<
        is_same<output_iterator_tag,
                typename iterator_traits<OutputIt>::iterator_category>::value ||
        (is_base_of<forward_iterator_tag, typename iterator_traits<OutputIt>::
                                              iterator_category>::value &&
         !is_const<OutputIt>::value)>::type>
void read(OutputIt __first, OutputIt __last) {
  for (; __first != __last; ++__first) read(*__first);
}
template <
    typename InputIt,
    typename = typename enable_if<is_base_of<
        input_iterator_tag,
        typename iterator_traits<InputIt>::iterator_category>::value>::type>
void wts(InputIt __first, InputIt __last) {
  bool isFirst = true;
  for (; __first != __last; ++__first) {
    if (isFirst)
      isFirst = false;
    else
      putchar(' ');
    write(*__first);
  }
  putchar('\n');
}
template <
    typename InputIt,
    typename = typename enable_if<is_base_of<
        input_iterator_tag,
        typename iterator_traits<InputIt>::iterator_category>::value>::type>
void wtb(InputIt __first, InputIt __last) {
  for (; __first != __last; ++__first) {
    write(*__first);
    putchar('\n');
  }
}
template <typename T>
void wts(const T& x) {
  write(x);
  putchar(' ');
}
template <typename T>
void wtb(const T& x) {
  write(x);
  putchar('\n');
}
template <typename T>
void wte(const T& x) {
  write(x);
  exit(0);
}
template <typename T, typename... Args>
void wts(const T& x, Args... args) {
  wts(x);
  wts(args...);
}
template <typename T, typename... Args>
void wtb(const T& x, Args... args) {
  wts(x);
  wtb(args...);
}
template <typename T, typename... Args>
void wte(const T& x, Args... args) {
  wts(x);
  wte(args...);
}
template <typename T>
inline bool up(T& x, const T& y) {
  return x < y ? x = y, 1 : 0;
}
template <typename T>
inline bool dn(T& x, const T& y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T>
inline bool inRange(const T& x, const T& l, const T& r) {
  return !(x < l) && !(r < x);
}
template <typename valueType, typename tagType>
class segmentTreeNode {
 public:
  int id, left, right;
  valueType val;
  tagType tag;
};
template <typename valueType, typename tagType,
          valueType (*merge)(valueType, valueType),
          void (*update)(segmentTreeNode<valueType, tagType>&, tagType)>
class segmentTree {
 private:
  std::vector<segmentTreeNode<valueType, tagType>> nodes;
  int leftRange, rightRange;
  valueType valueZero;
  tagType tagZero;
  void pushup(int cur) {
    nodes[cur].val = merge(nodes[cur << 1].val, nodes[cur << 1 | 1].val);
  }
  void pushdown(int cur) {
    update(nodes[cur << 1], nodes[cur].tag);
    update(nodes[cur << 1 | 1], nodes[cur].tag);
    nodes[cur].tag = tagZero;
  }
  void build(int cur, int l, int r, const std::vector<valueType>& initValue) {
    nodes[cur].id = cur;
    nodes[cur].left = l;
    nodes[cur].right = r;
    nodes[cur].tag = tagZero;
    if (l == r - 1)
      nodes[cur].val = initValue[l - leftRange];
    else {
      build(cur << 1, l, (l + r) >> 1, initValue);
      build(cur << 1 | 1, (l + r) >> 1, r, initValue);
      pushup(cur);
    }
  }
  void init(const std::vector<valueType>& _initValue,
            const valueType& _valueZero, const tagType& _tagZero) {
    valueZero = _valueZero;
    tagZero = _tagZero;
    nodes.resize((rightRange - leftRange) << 2);
    build(1, leftRange, rightRange, _initValue);
  }
  void modify(int cur, int l, int r, int L, int R, const tagType& tag) {
    if (l >= R || r <= L) return;
    if (L <= l && r <= R)
      update(nodes[cur], tag);
    else {
      pushdown(cur);
      modify(cur << 1, l, (l + r) >> 1, L, R, tag);
      modify(cur << 1 | 1, (l + r) >> 1, r, L, R, tag);
      pushup(cur);
    }
  }
  valueType query(int cur, int l, int r, int L, int R) {
    if (l >= R || r <= L) return valueZero;
    if (L <= l && r <= R) return nodes[cur].val;
    pushdown(cur);
    return merge(query(cur << 1, l, (l + r) >> 1, L, R),
                 query(cur << 1 | 1, (l + r) >> 1, r, L, R));
  }

 public:
  segmentTree() {}
  segmentTree(int _leftRange, int _rightRange,
              const std::vector<valueType>& _initValue,
              const valueType& _valueZero, const tagType& _tagZero) {
    leftRange = _leftRange;
    rightRange = _rightRange;
    init(_initValue, _valueZero, _tagZero);
  }
  segmentTree(int size, const std::vector<valueType>& _initValue,
              const valueType& _valueZero, const tagType& _tagZero) {
    leftRange = 1;
    rightRange = size + 1;
    init(_initValue, _valueZero, _tagZero);
  }
  void modify(int l, int r, const tagType& tag) {
    modify(1, leftRange, rightRange, l, r, tag);
  }
  void modify(int p, const tagType& tag) { modify(p, p + 1, tag); }
  valueType query(int l, int r) {
    return query(1, leftRange, rightRange, l, r);
  }
  valueType query(int p) { return query(p, p + 1); }
};
class maxFlow {
 private:
  std::queue<int> q;
  std::vector<int> head, cur, nxt, to, dep;
  std::vector<long long> cap;

 public:
  maxFlow(int _n = 0) { init(_n); }
  void init(int _n) {
    head.clear();
    head.resize(_n + 1, 0);
    nxt.resize(2);
    to.resize(2);
    cap.resize(2);
  }
  void init() { init(head.size() - 1); }
  void add(int u, int v, long long w) {
    nxt.push_back(head[u]);
    head[u] = to.size();
    to.push_back(v);
    cap.push_back(w);
  }
  void Add(int u, int v, long long w) {
    add(u, v, w);
    add(v, u, 0);
  }
  void del(int x) { cap[x << 1] = cap[x << 1 | 1] = 0; }
  bool bfs(int s, int t) {
    dep.clear();
    dep.resize(head.size(), -1);
    dep[s] = 0;
    q.push(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        long long w = cap[i];
        if (w > 0 && dep[v] == -1) {
          dep[v] = dep[u] + 1;
          q.push(v);
        }
      }
    }
    return ~dep[t];
  }
  long long dfs(int u, long long flow, int t) {
    if (dep[u] == dep[t]) return u == t ? flow : 0;
    long long out = 0;
    for (int& i = cur[u]; i; i = nxt[i]) {
      int v = to[i];
      long long w = cap[i];
      if (w > 0 && dep[v] == dep[u] + 1) {
        long long f = dfs(v, std::min(w, flow - out), t);
        cap[i] -= f;
        cap[i ^ 1] += f;
        out += f;
        if (out == flow) return out;
      }
    }
    return out;
  }
  long long maxflow(int s, int t) {
    long long out = 0;
    while (bfs(s, t)) {
      cur = head;
      out += dfs(s, 0x7fffffffffffffffll, t);
    }
    return out;
  }
  long long getflow(int x) const { return cap[x << 1 | 1]; }
};
struct customHash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = rng();
    return splitmix64(x + FIXED_RANDOM);
  }
};
struct Node {
  int val, ls, rs;
  bool l1;
  Node() {
    val = ls = rs = 0;
    l1 = false;
  }
};
vector<Node> t;
int modify(int u, int l, int r, int p, int x) {
  int cur = t.size();
  t.push_back(t[u]);
  t[cur].val += x;
  if (p == l) t[cur].l1 = x == 1;
  if (l == r - 1) return cur;
  if (p < ((l + r) >> 1))
    t[cur].ls = modify(t[u].ls, l, ((l + r) >> 1), p, x);
  else
    t[cur].rs = modify(t[u].rs, ((l + r) >> 1), r, p, x);
  return cur;
}
int query(int u, int l, int r, int k) {
  if (l == r - 1) return l;
  if (t[t[u].ls].val < k || (t[t[u].ls].val == k && !t[t[u].rs].l1))
    return query(t[u].rs, ((l + r) >> 1), r, k - t[t[u].ls].val);
  else
    return query(t[u].ls, l, ((l + r) >> 1), k);
}
int n;
vector<int> a, rt, pre;
int solve(int k) {
  int p = 0, out = 0;
  while (p < n) {
    ++out;
    p = query(rt[p], 0, n, k) + 1;
  }
  return out;
}
signed main() {
  read(n);
  a.resize(n);
  rt.resize(n + 1, 0);
  pre.resize(n + 1, -1);
  read(a.begin(), a.end());
  t.resize(1);
  t.reserve(5000000);
  for (int i = (n - 1), iend = (0); i >= iend; --i) {
    rt[i] = modify(rt[i + 1], 0, n, i, 1);
    if (~pre[a[i]]) rt[i] = modify(rt[i], 0, n, pre[a[i]], -1);
    pre[a[i]] = i;
  }
  for (int i = (1), iend = (n); i <= iend; ++i) wts(solve(i));
  return 0;
}
