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]
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        new Main().solve();
    }

    int inf = 2000000000;
    int mod = 1000000007;
    double eps = 0.00000001;

    PrintWriter out;

    int n;
    int m;

    ArrayList<Pair>[] g = new ArrayList[2000000];

    int z = 400010;

    void solve() throws IOException {

        Reader in;
        BufferedReader br;

        try {

            //br = new BufferedReader( new FileReader("input.txt") );
            in = new Reader("input.txt");
            out = new PrintWriter( new BufferedWriter(new FileWriter("output.txt")) );
        }
        catch (Exception e) {

            //br = new BufferedReader( new InputStreamReader( System.in ) );
            in = new Reader();
            out = new PrintWriter( new BufferedWriter(new OutputStreamWriter(System.out)) );
        }

        n = in.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = in.nextInt();

        int[] last = new int[1000010];
        Arrays.fill(last, -1);

        Node root = build(0, n-1);

        long time = System.currentTimeMillis();

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

            int x = a[i];
            if (last[x] != -1)
                root = add(root, 0, n-1, last[x], -1);
            last[x] = i;
            root = add(root, 0, n-1, last[x], 1);
            roots[i] = root;
        }

        //System.err.println(System.currentTimeMillis() - time);
        //System.err.println(get(roots[5], 0, n-1, 3, 5));

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

            int pos = n-1;
            int ans = 0;
            while (pos >= 0) {

                pos = next(roots[pos], 0, n-1, pos, i+1);
                ans++;
                //System.err.println(pos+" "+i);
            }

            out.print(ans+" ");
            //System.err.println(System.currentTimeMillis()-time);
        }

        //System.err.println(System.currentTimeMillis() - time);

        out.flush();
        out.close();
    }

    int find(int ll, int k) {

        int r = n-1;
        int l = ll;
        int pos = l;

        while (l <= r) {

            int x = (l+r)/2;
            if (get(roots[x], 0, n-1, ll, n-1) <= k) {
                pos = x;
                l = x+1;
            }
            else {
                r = x-1;
            }
        }

        return pos+1;
    }

    int next(Node v, int tl, int tr, int l, int k) {

        if (k >= v.val)
            return tl-1;

        //System.err.println(tl+" "+tr+" "+k+" "+v.val);

        if (tl == tr)
            return tl;

        int tm = (tl+tr)/2;

        if (v.r.val <= k) {
            return next(v.l, tl, tm, l, k - v.r.val);
        }
        else
            return next(v.r, tm+1, tr, l, k);
    }

    class Node {

        Node l = null;
        Node r = null;
        int val = 0;
    }

    Node[] t = new Node[400000];
    int sz = 0;
    Node[] roots = new Node[400000];

    Node build(int tl, int tr) {

        Node node = new Node();
        if (tl == tr)
            return node;

        int tm = (tl+tr)/2;
        node.l = build(tl, tm);
        node.r = build(tm+1, tr);

        return node;
    }

    Node add(Node v, int tl, int tr, int pos, int x) {

        Node node = new Node();
        node.l = v.l;
        node.r = v.r;
        node.val = v.val+x;

        //System.err.println(tl+" "+tr+" "+node.val+" "+pos);

        if (tl == tr) {
            return node;
        }

        int tm = (tl+tr)/2;

        if (pos <= tm) {

            node.l = add(v.l, tl, tm, pos, x);
        }
        else {

            node.r = add(v.r, tm+1, tr, pos, x);
        }

        return node;
    }

    int get(Node v, int tl, int tr, int l, int r) {

        if (v == null)
            return 0;

        if (l > r)
            return 0;

        if (tl == l && tr == r)
            return v.val;

        int tm = (tl+tr)/2;

        return get(v.l, tl, tm, l, Math.min(tm, r)) + get(v.r, tm+1, tr, Math.max(tm+1, l), r);
    }

    class Pair implements Comparable<Pair>{

        int a;
        long b;


        Pair(int a, long b) {

            this.a = a;
            this.b = b;

        }

        public int compareTo(Pair p) {
            if (b > p.b) return 1;
            if (b < p.b) return -1;
            if (a > p.a) return 1;
            if (a < p.a) return -1;
            return 0;
        }
    }

    class Item {

        int a;
        int b;
        int c;

        Item(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

    }

    class Reader {

        BufferedReader  br;
        StringTokenizer tok;

        Reader(String file) throws IOException {
            br = new BufferedReader( new FileReader(file) );
        }

        Reader() throws IOException {
            br = new BufferedReader( new InputStreamReader(System.in) );
        }

        String next() throws IOException {

            while (tok == null || !tok.hasMoreElements())
                tok = new StringTokenizer(br.readLine());
            return tok.nextToken();
        }

        int nextInt() throws NumberFormatException, IOException {
            return Integer.valueOf(next());
        }

        long nextLong() throws NumberFormatException, IOException {
            return Long.valueOf(next());
        }

        double nextDouble() throws NumberFormatException, IOException {
            return Double.valueOf(next());
        }


        String nextLine() throws IOException {
            return br.readLine();
        }

    }

}