Nikita plays a new computer game. There are m levels in this game. In the beginning of each level a new class appears in the game; this class is a child-class of the class yi (and yi is called parent-class for this new class). Thus, the classes form a tree. Initially there is only one class with index 1.

Changing the class to its neighbour (child-class or parent-class) in the tree costs 1 coin. You can not change the class back. The cost of changing the class a to the class b is equal to the total cost of class changes on the path from a to b in the class tree.

Suppose that at i -th level the maximum cost of changing one class to another is x. For each level output the number of classes such that for each of these classes there exists some other class y, and the distance from this class to y is exactly x.

Input

First line contains one integer number m — number of queries (1 ≤ m ≤ 3·105).

Next m lines contain description of queries. i -th line (1 ≤ i ≤ m) describes the i -th level and contains an integer yi — the index of the parent-class of class with index i + 1 (1 ≤ yi ≤ i). 

Output

Suppose that at i -th level the maximum cost of changing one class to another is x. For each level output the number of classes such that for each of these classes there exists some other class y, and the distance from this class to y is exactly x.

Examples

Input

4
1
1
2
1


Output

2
2
2
3


Input

4
1
1
2
3


Output

2
2
2
2
import java.io.*;
import java.util.*;

public class Template implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    void init() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            String filename = "";
            if (filename.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(filename + ".in"));
                out = new PrintWriter(filename + ".out");
            }
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            try {
                tok = new StringTokenizer(in.readLine(), " :");
            } catch (Exception e) {
                return null;
            }
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    int[] readIntArray(int size) throws IOException {
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = readInt();
        }
        return res;
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    <T> List<T>[] createGraphList(int size) {
        List<T>[] list = new List[size];
        for (int i = 0; i < size; i++) {
            list[i] = new ArrayList<>();
        }
        return list;
    }

    public static void main(String[] args) {
        new Template().run();
        //new Thread(null, new Template(), "", 1l * 200 * 1024 * 1024).start();
    }

    long timeBegin, timeEnd;

    void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    long memoryTotal, memoryFree;

    void memory() {
        memoryFree = Runtime.getRuntime().freeMemory();
        System.err.println("Memory = " + ((memoryTotal - memoryFree) >> 10)
                + " KB");
    }

    public void run() {
        try {
            timeBegin = System.currentTimeMillis();
            memoryTotal = Runtime.getRuntime().freeMemory();
            init();
            solve();
            out.close();
            if (System.getProperty("ONLINE_JUDGE") == null) {
                time();
                memory();
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

    int[] h;
    List<Integer>[] graph;
    List<Integer> orderList = new ArrayList<>();

    void dfs(int x, int height) {
        orderList.add(x);
        h[x] = height;
        for (int y : graph[x]) {
            dfs(y, height + 1);
            orderList.add(x);
        }
    }

    class SparseTable {

        int[] data;
        int[][] minIndex;
        int[] powers;

        int levels = 20;

        SparseTable(int[] data) {
            this.data = data;
            minIndex = new int[levels][data.length];
            for (int i = 0; i < data.length; i++) {
                minIndex[0][i] = i;
            }
            for (int l = 1; l < levels; l++) {
                for (int i = 0; i < data.length; i++) {
                    int second = i + (1 << (l - 1));
                    if (second >= data.length) break;

                    if (data[minIndex[l - 1][i]] < data[minIndex[l - 1][second]]) {
                        minIndex[l][i] = minIndex[l - 1][i];
                    } else {
                        minIndex[l][i] = minIndex[l - 1][second];
                    }
                }
            }

            powers = new int[data.length];
            int p2 = 1;
            int z = 0;
            while (p2 < data.length) {
                powers[p2] = z;
                z++;
                p2 *= 2;
            }
            for (int i = 2; i < powers.length; i++) {
                if (powers[i] == 0) {
                    powers[i] = powers[i - 1];
                }
            }
        }

        int getMinIndex(int l, int r) {
            if (l > r) return getMinIndex(r, l);
            int len = r - l + 1;
            int level = powers[len];
            int size = 1 << level;

            int i1 = minIndex[level][l];
            int i2 = minIndex[level][r - size + 1];
            if (data[i1] < data[i2]) return i1;
            return i2;
        }

    }

    void solve() throws IOException {
        int m = readInt();
        int[] q = readIntArray(m);
        graph = new List[m + 1];
        for (int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < q.length; i++) {
            int a = q[i] - 1;
            int b = i + 1;
            graph[a].add(b);
        }
        h = new int[m + 1];
        dfs(0, 0);

        order = new int[orderList.size()];
        int[] data = new int[order.length];
        for (int i = 0; i < orderList.size(); i++) {
            order[i] = orderList.get(i);
            data[i] = h[order[i]];
        }

        st = new SparseTable(data);
        first = new int[m + 1];
        Arrays.fill(first, -1);
        for (int i = 0; i < order.length; i++) {
            if (first[order[i]] == -1) {
                first[order[i]] = i;
            }
        }

        int a = 0;
        int b = 0;
        int currentD = 0;

        int[] d1 = new int[m];
        int[] d2 = new int[m];
        int[] diam = new int[m];

        for (int i = 0; i < m; i++) {
            int nextD1 = dist(a, i + 1);
            int nextD2 = dist(b, i + 1);
            int nextD = Math.max(nextD1, nextD2);
            if (nextD > currentD) {
                if (nextD1 > nextD2) {
                    b = i + 1;
                } else {
                    a = i + 1;
                }
                currentD = nextD;
            }
            d1[i] = a;
            d2[i] = b;
            diam[i] = currentD;
        }
        int[] cntStart = new int[m];
        int[] cntEnd = new int[m];
        for (int i = 0; i < m; i++) {
            int l = i;
            int r = m - 1;
            int answer = findTo(l, r, d1, d2, diam, i + 1);

            if (answer > -1) {
                cntStart[i]++;
                cntEnd[answer]++;
            }
        }

        int answer = findTo(0, m - 1, d1, d2, diam, 0);

        int res = 0;
        if (answer > -1) {
            res = 1;
            cntEnd[answer]++;
        }
        for (int i = 0; i < m; i++) {
            res += cntStart[i];
            out.println(res);
            res -= cntEnd[i];
        }
    }

    int findTo(int l, int r, int[] d1, int[] d2, int[] diam, int x) {
        int answer = -1;

        while (l <= r) {
            int mid = (l + r) >> 1;
            int d = Math.max(dist(d1[mid], x), dist(d2[mid], x));
            if (d == diam[mid]) {
                answer = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return answer;
    }

    SparseTable st;
    int[] order;
    int[] first;

    int dist(int a, int b) {
        int lca = lca(a, b);
        return h[a] + h[b] - 2 * h[lca];
    }

    int lca(int a, int b) {
        int index = st.getMinIndex(first[a], first[b]);
        return order[index];
    }

}