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.util.*;
import java.io.*;
public class B{
	static int n;
	static List<Integer>[] adj;
	static int[][] up;
	static int[] par;
	static int[] depth;
	
	static void dfs(int src, int p, int d)
	{
		par[src] = p;
		depth[src] = d;
		for(int i:adj[src])
		{
			if(i == p)continue;
			dfs(i,src,d+1);
		}
	}
	
	static int getLca(int u, int v)
	{
		if(depth[v]>depth[u])
		{
			int temp = u;
			u = v;
			v = temp;
		}
		int finu = u; int finv = v;
		int diff = depth[u] - depth[v];
		for(int jump=20;jump>=0;jump--)
		{
			if((1<<jump)<=diff)
			{
				diff -= (1<<jump);
				u = up[u][jump];
			}
		}
		if(u == v)
		{
			return u;
		}
		else
		{
			for(int jump=20;jump>=0;jump--)
			{
				if(up[u][jump] != up[v][jump])
				{
					u = up[u][jump];
					v = up[v][jump];
				}
			}
			return par[u];
		}
	}
	
	static int get(int u, int v)
	{
		int lca = getLca(u,v);
		return depth[u] + depth[v] - 2*depth[lca];
	}
	
	public static void main(String[] args)
	{
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		n = fs.nextInt();
		adj = new ArrayList[n+1];
		for(int i=1;i<=n;i++)adj[i] = new ArrayList();
		int a = fs.nextInt(); // dummy
		adj[1].add(2); adj[2].add(1);
		
		int u = 3;
		for(int i=0;i<n-2;i++)
		{
			int v = fs.nextInt();
			adj[u].add(v); adj[v].add(u);
			u++;
		}
		depth = new int[n+1];
		par = new int[n+1];
		up = new int[n+1][21];
		
		dfs(1,-1,0);
		
		for(int i=0;i<=20;i++)up[1][i] = -1;
		for(int i=2;i<=n;i++)up[i][0] = par[i];
		
		for(int jump=1;jump<=20;jump++)
		{
			for(int node=2;node<=n;node++)
			{
				if(up[node][jump-1] == -1)up[node][jump] = -1;
				else up[node][jump] = up[up[node][jump-1]][jump-1];
			}
		}
		
		out.print("1 ");
		int x = 1; int y = 2;
		int max = 1;
		for(int i=3;i<=n;i++)
		{
			int d2 = get(x,i);
			int d3 = get(y,i);
			if(d2>d3)
			{
				if(d2>max)
				{
					max = d2;
					y = i;
				}
			}
			else
			{
				if(d3>max)
				{
					max = d3;
					x = i;
				}
			}
			out.print(max+" ");
		}
		out.println();
		out.close();
	}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	public static int[] sort(int[] arr)
	{
		List<Integer> temp = new ArrayList();
		for(int i:arr)temp.add(i);
		Collections.sort(temp,Collections.reverseOrder());
		int start = 0;
		for(int i:temp)arr[start++]=i;
		return arr;
	}
}