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;
int n, root = 0;
vector<int> v[200001];
int tin[200001], tout[200001];
int p[200001][25];
int d[200001];
int current = 0, u = 0, w = 0, curd = 0;
void dfs(int a, int depth) {
  d[a] = depth;
  current++;
  tin[a] = current;
  for (int i = 0; i < v[a].size(); i++) dfs(v[a][i], depth + 1);
  current++;
  tout[a] = current;
}
void dfs1(int a) {
  int cur = 0;
  if (p[a][0] == -1) goto m1;
  while (p[p[a][cur]][cur] != -1) {
    p[a][cur + 1] = p[p[a][cur]][cur];
    cur++;
  }
m1:
  for (int i = 0; i < v[a].size(); i++) dfs1(v[a][i]);
}
bool isanc(int a, int b) {
  if (a == -1) return true;
  if (tin[a] < tin[b] && tout[a] > tout[b]) return true;
  return false;
}
int diametr(int a, int b) {
  if (isanc(a, b) || isanc(b, a)) return abs(d[a] - d[b]);
  int l = 20;
  int pr = a;
  while (l) {
    if (isanc(p[pr][l - 1], b))
      l--;
    else
      pr = p[pr][l - 1];
  }
  return d[a] - d[p[pr][0]] + d[b] - d[p[pr][0]];
}
int main() {
  int a;
  cin >> n;
  p[0][0] = -1;
  for (int i = 1; i < n; i++) {
    cin >> a;
    a--;
    v[a].push_back(i);
    p[i][0] = a;
  }
  dfs(root, 0);
  for (int i = 0; i < n; i++)
    for (int j = 1; j < 20; j++) p[i][j] = -1;
  dfs1(root);
  for (int i = 1; i < n; i++) {
    int newd1 = diametr(w, i);
    int newd2 = diametr(u, i);
    if (newd1 > newd2) {
      if (newd1 > curd) {
        u = i;
        curd = newd1;
      }
    } else {
      if (newd2 > curd) {
        w = i;
        curd = newd2;
      }
    }
    cout << curd << '\n';
  }
  return 0;
}
