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 
#include <bits/stdc++.h>
using namespace std;
vector<int> E[201000];
int n, cnt, res, Dep[201000], par[201000][18];
int Num[201000], Ed[201000];
void DFS(int a) {
  int i;
  Num[a] = ++cnt;
  for (i = 0; i < E[a].size(); i++) {
    Dep[E[a][i]] = Dep[a] + 1;
    par[E[a][i]][0] = a;
    DFS(E[a][i]);
  }
  Ed[a] = cnt;
}
int LCA(int a, int b) {
  if (Dep[a] < Dep[b]) return LCA(b, a);
  int d = Dep[a] - Dep[b], i = 0;
  while (d) {
    if (d & 1) a = par[a][i];
    d >>= 1;
    i++;
  }
  for (i = 17; i >= 0; i--) {
    if (par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
  }
  if (a != b) a = par[a][0];
  return a;
}
int Dist(int a, int b) {
  int L = LCA(a, b);
  return Dep[a] + Dep[b] - Dep[L] * 2;
}
int main() {
  int i, a, b, j;
  scanf("%d", &n);
  for (i = 2; i <= n; i++) {
    scanf("%d", &a);
    E[a].push_back(i);
  }
  DFS(1);
  res = 1;
  for (i = 0; i < 17; i++) {
    for (j = 1; j <= n; j++) {
      par[j][i + 1] = par[par[j][i]][i];
    }
  }
  for (i = 2; i <= n; i++) {
    if (i == 2) {
      printf("%d ", res);
      a = 1, b = 2;
      continue;
    }
    int d1, d2;
    d1 = Dist(a, i);
    d2 = Dist(b, i);
    if (d1 > res && d1 >= d2) {
      res = d1;
      b = i;
    } else if (d2 > res) {
      res = d2;
      a = i;
    }
    printf("%d ", res);
  }
}
