Breaking news from zombie neurology! It turns out that – contrary to previous beliefs – every zombie is born with a single brain, and only later it evolves into a complicated brain structure. In fact, whenever a zombie consumes a brain, a new brain appears in its nervous system and gets immediately connected to one of the already existing brains using a single brain connector. Researchers are now interested in monitoring the brain latency of a zombie. Your task is to write a program which, given a history of evolution of a zombie's nervous system, computes its brain latency at every stage.

Input

The first line of the input contains one number n – the number of brains in the final nervous system (2 ≤ n ≤ 200000). In the second line a history of zombie's nervous system evolution is given. For convenience, we number all the brains by 1, 2, ..., n in the same order as they appear in the nervous system (the zombie is born with a single brain, number 1, and subsequently brains 2, 3, ..., n are added). The second line contains n - 1 space-separated numbers p2, p3, ..., pn, meaning that after a new brain k is added to the system, it gets connected to a parent-brain <image>.

Output

Output n - 1 space-separated numbers – the brain latencies after the brain number k is added, for k = 2, 3, ..., n.

Example

Input

6
1
2
2
1
5


Output

1 2 2 3 4 
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Solver {
    private BufferedReader in;
    private PrintWriter out;

    Solver() throws IOException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter(new FileWriter("output.txt"));
        } catch (Exception ex) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }
        try {
            solve();
        } finally {
            try {
                in.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            out.close();
        }
    }

    public static void main(String[] args) throws IOException {
        new Solver();
    }

    StringTokenizer st;

    String next() throws IOException {
        while (st == null || !st.hasMoreElements())
            st = new StringTokenizer(in.readLine());
        return st.nextToken();
    }

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

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

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

    boolean[] used;
    int[] depth;
    int[][] pa;
    List<Integer>[] adj;

    private void dfs(int u, int parent, int d) {
        used[u] = true;
        depth[u] = d;
        pa[u][0] = parent;
        for(int v : adj[u]) {
            if (!used[v])
                dfs(v, u, d+1);
        }
    }

    private void addOne(int u, int v) {
        for (int i = 1; i < 24; i++) {
            pa[v][i] = pa[pa[v][i-1]][i-1];
        }
    }

    public int lca(int u, int v) {
        if (depth[u] < depth[v]) {
            int t = u;
            u = v;
            v = t;
        }
        for (int i = 23; i >= 0; i--) {
            if (depth[u] - (1 << i) >= depth[v])
                u = pa[u][i];
        }
        if (u == v) return u;
        return lca2(u, v);
    }

    private int lca2(int u, int v) {
        for (int i = 23; i >= 0; i--) {
            if (pa[u][i] != pa[v][i] && pa[u][i] != -1) {
                u = pa[u][i];
                v = pa[v][i];
            }
        }
        return pa[u][0];
    }

    private int dist(int u, int v) {
        return depth[u] + depth[v] - 2*depth[lca(u, v)];
    }

    private void solve() throws IOException {
        int n = nextInt();
        depth = new int[n+1];
        pa = new int[n+1][24];
        used = new boolean[n+1];

        depth[0] = -1;

        adj = new List[n+1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        int bx = 1;
        int by = 1;
        for (int i = 2; i <= n; i++) {
            int from = nextInt();
            adj[from].add(i);
            dfs(i, from, depth[from] + 1);
            addOne(from, i);
            int ox = bx;
            int oy = by;
            if (dist(ox, i) > dist(bx, by)) {
                bx = ox;
                by = i;
            }
            if (dist(i, oy) > dist(bx, by)) {
                bx = i;
                by = oy;
            }
            out.print(dist(bx, by));
            out.print(" ");
        }

    }

}
