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.*;

public class BrainNetworkHard {

	static int maxn = 200002;
	static int[] ord = new int[2*maxn], dep = new int[2*maxn], fst = new int[maxn];
	static ArrayList<Integer>[] tr = new ArrayList[maxn];
	static int[][] spt = new int[2*maxn][ (int) Math.ceil(Math.log(2*maxn)/Math.log(2.0)) ];
	static int n,idx;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String s;
		int m,i,j,k,l;
		int x,y,w,u,v;
		int[] fat = new int[maxn];
		
		s = br.readLine();
		n = Integer.parseInt(s);
		
		fat[1] = 1;
		tr[1] = new ArrayList();
		for(i=2;i<=n;i++) {
			tr[i] = new ArrayList();
			s = br.readLine();
			fat[i] = Integer.parseInt(s);
			tr[fat[i]].add(i);
		}
		
//		for(i=1;i<=n;i++) System.out.println(tr[i]);
		idx = 0;
		dfs(1,0);
		
		for(i=0;i<2*n-1;i++) spt[i][0] = i;
		
		for(j=1;(1<<j)<=2*n-1;j++) {
			
			for(i=0; i+(1<<j)-1 < 2*n-1 ;i++) {
				u = spt[i][j-1];
				v = spt[i + (1<<(j-1))][j-1];
				if (dep[u]<dep[v]) spt[i][j] = u;
				else spt[i][j] = v;
			}
		}
		
		x = y = 1;
		int max = 0,tx,ty;
		
		for(i=2;i<=n;i++) {
			
//			System.out.println(i+" "+x+" "+y+" "+max);
	//		System.out.println(dep[fst[i]]+" "+dep[fst[x]]+" "+dep[fst[y]]);
			tx = dist(x,i); ty = dist(y,i);
	//		System.out.println(tx+" "+ty);
			if ((tx>max) && (tx>=ty)) {
				y = i;
				max = tx;
			}
			
			if ((ty>max) && (ty>tx)) {
				x = i;
				max = ty;
			}
			
			if (i!=n) bw.write(max+" ");
			else bw.write(max+"\n");
		}
//		System.out.println(x+" "+y+" "+max);
		bw.close();
	}
	
	public static int dist(int u, int v) {
		int lca;
		if (fst[u]<fst[v]) lca = ord[rmq(fst[u],fst[v])];
		else lca = ord[rmq(fst[v],fst[u])];
		int depu = dep[fst[u]], depv = dep[fst[v]], deplca = dep[fst[lca]];
//		System.out.println(u+" "+v+" "+lca+" "+depu+" "+depv+" "+deplca);
		return depu + depv - 2*deplca;
	}
	
	public static int rmq(int a, int b) {
		int k = (int) Math.floor(Math.log(b-a+1)/Math.log(2.0));
		int c1 = spt[a][k], c2 = spt[b-(1<<k)+1][k];
		if (dep[c1]<dep[c2]) return c1;
		else return c2;
	}

	public static void dfs(int u, int depth) {
		int i;
		
		fst[u] = idx;
		ord[idx] = u;
		dep[idx] = depth;
		idx++;
		
		for(i=0;i<tr[u].size();i++) {
			dfs(tr[u].get(i),depth+1);
			ord[idx] = u;
			dep[idx] = depth;
			idx++;
		}
		
	}
}
