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;
const int max_n = 400005;
const int max_m = 25;
struct edge {
  int to, next, cost;
} es[2 * max_n];
int cnt = 0;
int head[max_n];
void add(int u, int v) {
  es[cnt].to = v;
  es[cnt].next = head[u];
  es[cnt].cost = 1;
  head[u] = cnt++;
}
int depth[max_n << 1];
int first[max_n << 1];
int dir[max_n << 1];
int que[max_n << 1];
int dp[max_n][20];
bool vis[max_n];
int tot = 0;
void dfs(int u, int dep) {
  vis[u] = true;
  que[++tot] = u;
  first[u] = tot;
  depth[tot] = dep;
  for (int k = head[u]; k != -1; k = es[k].next) {
    int v = es[k].to, cost = es[k].cost;
    if (!vis[v]) {
      dir[v] = dir[u] + cost;
      dfs(v, dep + 1);
      que[++tot] = u;
      depth[tot] = dep;
    }
  }
}
void ST(int n) {
  for (int i = 1; i <= n; i++) dp[i][0] = i;
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      int a = dp[i][j - 1], b = dp[i + (1 << (j - 1))][j - 1];
      dp[i][j] = depth[a] < depth[b] ? a : b;
    }
  }
}
int RMQ(int l, int r) {
  int k = 0;
  while ((1 << (k + 1)) <= r - l + 1) k++;
  int a = dp[l][k], b = dp[r - (1 << k) + 1][k];
  return depth[a] < depth[b] ? a : b;
}
int LCA(int u, int v) {
  int x = first[u], y = first[v];
  if (x > y) swap(x, y);
  int res = RMQ(x, y);
  return que[res];
}
int x[max_n];
int main() {
  int p, q;
  int n;
  for (int i = 0; i < max_n; i++) {
    head[i] = -1;
    vis[i] = false;
  }
  scanf("%d", &n);
  for (int i = 2; i <= n; i++) {
    scanf("%d", x + i);
    add(i, x[i]);
    add(x[i], i);
  }
  dfs(1, 1);
  ST(2 * n - 1);
  int da = 1, db = 1;
  int d = 0;
  for (int i = 2; i <= n; i++) {
    int lca1 = LCA(i, da);
    int tmp1 = dir[i] + dir[da] - 2 * dir[lca1];
    int lca2 = LCA(i, db);
    int tmp2 = dir[i] + dir[db] - 2 * dir[lca2];
    if (tmp1 < tmp2) {
      if (tmp2 > d) {
        da = i;
        d = tmp2;
      }
    } else {
      if (tmp1 > d) {
        db = i;
        d = tmp1;
      }
    }
    printf("%d ", d);
  }
  return 0;
}
