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.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;

/**
 *
 * @author Admin
 */
public class A {
	final static int maxLayer = 20;
	static List<List<Integer>> parent;
	static int[] height;
	
	static int lca(int x, int y) {
		if (height[x] < height[y]) {
			int tmp = x; x = y; y = tmp;
		}
		int iLayer = maxLayer, diff = height[x] - height[y];
		while (diff != 0) {
			--iLayer;
			if (diff - (1<<iLayer) >= 0) {
				diff -= 1<<iLayer;
				x = parent.get(x).get(iLayer);
			}
		}
		assert height[x] == height[y];
		iLayer = maxLayer;
		while (iLayer != 0) {
			--iLayer;
			assert iLayer != -1;
			assert x != -1;
			assert y != -1;
			if (!Objects.equals(parent.get(x).get(iLayer), parent.get(y).get(iLayer))) {
				x = parent.get(x).get(iLayer);
				y = parent.get(y).get(iLayer); 
			}
		}
		return x == y ? x : parent.get(x).get(0);
	}
	
	static int dist(int x, int y) {
		int lca = lca(x, y);
		assert lca != -1;
		return height[x] - height[lca] + height[y] - height[lca];
	}
	
	public static void main(String[] args) {
		// ClassLoader.getSystemClassLoader().setDefaultAssertionStatus(true);
		
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		parent = new ArrayList<>();
		height = new int[n]; height[0] = 0;
		for (int i = 0; i < n; ++i)
			parent.add(new ArrayList<>(Collections.nCopies(maxLayer, -1))); // parent[n][x] = 2^x'th parent of n
		for (int i = 1; i < n; ++i) {
			int par_i = in.nextInt()-1;
			parent.get(i).set(0, par_i);
			height[i] = 1+height[par_i];
		}
		for (int nLayer = 1; nLayer < maxLayer; ++nLayer)
			for (int i = 0; i < n; ++i) {
				int p = parent.get(i).get(nLayer-1);
				if (p != -1) p = parent.get(p).get(nLayer-1);
				parent.get(i).set(nLayer, p); // verbose?
			}
		int end1 = 0, end2 = 0, d = 0;
		for (int i = 1; i < n; ++i) {
			int d1 = dist(i, end1), d2 = dist(i, end2);
			if (d1 > d) {
				end2 = i;
				d = d1;
			} else if (d2 > d) {
				end1 = i;
				d = d2;
			}
			System.out.print(d + " ");
		}
		System.out.println();
	}
}

	   	  						 				  							 		