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 maxm = 2e5 + 10;
struct side {
  int x, y, w;
  side() {}
  side(int xx, int yy, int ww) {
    x = xx;
    y = yy;
    w = ww;
  }
} source[maxm];
struct self {
  int y, w, nxt;
} s[maxm * 2];
int fst[maxm];
int m, tn, n, q;
int x, y, w;
int dep[maxm], top[maxm], siz[maxm], fa[maxm], son[maxm];
int base[maxm];
int POS[maxm];
int tot;
int f[maxm << 2];
int pos;
void dfs(int u) {
  siz[u] = 1;
  for (int e = fst[u]; e != -1; e = s[e].nxt) {
    int v = s[e].y;
    if (v != fa[u]) {
      fa[v] = u;
      dep[v] = dep[u] + 1;
      dfs(v);
      siz[u] += siz[v];
      if (son[u] == -1 || siz[son[u]] < siz[v]) son[u] = v;
    }
  }
}
void profile(int u, int t) {
  top[u] = t;
  POS[u] = ++tot;
  if (son[u] != -1 && son[u] != 0) profile(son[u], t);
  for (int e = fst[u]; e != -1; e = s[e].nxt) {
    int v = s[e].y;
    if (v != fa[u] && v != son[u]) profile(v, v);
  }
}
void pushup(int o) { f[o] = f[o << 1] + f[o << 1 | 1]; }
void build(int o, int l, int r) {
  if (l == r) {
    f[o] = base[l];
    return;
  }
  int mid = (l + r) >> 1;
  build(o << 1, l, mid);
  build(o << 1 | 1, mid + 1, r);
  pushup(o);
}
int query(int o, int l, int r, int x, int y) {
  if (l >= x && r <= y) return f[o];
  int mid = (l + r) >> 1;
  int ret = 0;
  if (x <= mid) ret += query(o << 1, l, mid, x, y);
  if (y > mid) ret += query(o << 1 | 1, mid + 1, r, x, y);
  return ret;
}
void update(int o, int l, int r, int x, int y) {
  if (l == r) {
    f[o] = y;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(o << 1, l, mid, x, y);
  else
    update(o << 1 | 1, mid + 1, r, x, y);
  pushup(o);
}
int Q(int x, int y) {
  int ans = 0;
  int fx = top[x], fy = top[y];
  while (fx != fy) {
    if (dep[fx] < dep[fy]) {
      swap(x, y);
      swap(fx, fy);
    }
    ans += query(1, 1, tot, POS[fx], POS[x]);
    x = fa[fx];
    fx = top[x];
  }
  if (x != y) {
    if (dep[x] < dep[y]) swap(x, y);
    ans += query(1, 1, tot, POS[y] + 1, POS[x]);
  }
  return ans;
}
void U(int x, int y) {
  int l = source[x].x;
  int r = source[x].y;
  if (dep[l] < dep[r]) swap(l, r);
  update(1, 1, tot, POS[l], y);
}
void add(int x, int y, int w) {
  n++;
  s[n].y = y;
  s[n].w = w;
  s[n].nxt = fst[x];
  fst[x] = n;
}
int main() {
  scanf("%d", &m);
  tn = m - 1;
  n = 0;
  memset(fst, -1, sizeof(fst));
  for (int i = 1; i <= tn; i++) {
    x = i + 1;
    scanf("%d", &y);
    source[i] = side(x, y, 1);
    add(x, y, 1);
    add(y, x, 1);
  }
  fa[1] = 1;
  dep[1] = 1;
  memset(son, -1, sizeof(son));
  dfs(1);
  top[1] = 1;
  tot = 0;
  profile(1, 1);
  for (int i = 1; i <= tn; i++) {
    int x;
    if (dep[source[i].x] < dep[source[i].y])
      x = source[i].y;
    else
      x = source[i].x;
    base[POS[x]] = source[i].w;
  }
  build(1, 1, tot);
  int l = 1;
  int r = 2;
  int dist = 1;
  vector<int> ans;
  ans.push_back(1);
  for (int i = 3; i <= m; i++) {
    int l1 = l;
    int r1 = i;
    int dist1 = Q(l1, r1);
    int l2 = i;
    int r2 = r;
    int dist2 = Q(l2, r2);
    if (dist1 > dist) {
      l = l1;
      r = r1;
      dist = dist1;
    } else if (dist2 > dist) {
      l = l2;
      r = r2;
      dist = dist2;
    }
    ans.push_back(dist);
  }
  for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
  cout << endl;
  return 0;
}
