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> vec[200005];
int p[200005][20];
bool visited[200005];
int tin[200005], tout[200005];
int depth[200005];
int v = 0, u = 0, maxd = 0, time1 = 0;
bool isans(int a, int b) {
  if (a == -1) return true;
  if (a == b) return true;
  if (tin[a] <= tin[b] && tout[b] <= tout[a])
    return true;
  else
    return false;
}
int dist(int a, int b) {
  if (isans(a, b)) return depth[b] - depth[a];
  if (isans(b, a)) return depth[a] - depth[b];
  int l = 19, curv = a;
  while (l != -1) {
    if (isans(p[curv][l], b))
      l--;
    else {
      curv = p[curv][l];
    }
  }
  int lca = p[curv][0];
  return depth[a] - 2 * depth[lca] + depth[b];
}
void dfs(int a, int d) {
  time1++;
  depth[a] = d;
  tin[a] = time1;
  visited[a] = true;
  for (int i = 0; i < vec[a].size(); i++)
    if (!visited[vec[a][i]]) dfs(vec[a][i], d + 1);
  tout[a] = time1;
  time1++;
}
int main() {
  int n, a;
  cin >> n;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < 20; j++) p[i][j] = -1;
  for (int i = 1; i < n; i++) {
    cin >> a;
    a--;
    vec[a].push_back(i);
    vec[i].push_back(a);
    p[i][0] = a;
  }
  dfs(0, 0);
  for (int i = 0; i < n; i++) {
    int cur = 0;
    while (p[i][cur] != -1) {
      p[i][cur + 1] = p[p[i][cur]][cur];
      cur++;
    }
  }
  for (int i = 1; i < n; i++) {
    int d1 = dist(v, i);
    int d2 = dist(u, i);
    if (max(d1, d2) <= maxd) {
      cout << maxd << endl;
      continue;
    }
    if (d1 > d2) {
      maxd = d1;
      u = i;
    } else {
      maxd = d2;
      v = i;
    }
    cout << maxd << endl;
  }
  return 0;
}
