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, i, j, u, v, ans, deep[200010], t[200010][21];
void dfs(int u) {
  if (!deep[t[u][0]]) dfs(t[u][0]);
  deep[u] = deep[t[u][0]] + 1;
}
int len(int u, int v) {
  if (deep[u] < deep[v]) swap(u, v);
  int ans = deep[u] - deep[v], i;
  for (i = 20; deep[u] - deep[v]; i--)
    if ((1 << i) <= deep[u] - deep[v]) u = t[u][i];
  for (i = 20; u != v && i != -1; i--)
    if (t[u][i] != t[v][i]) ans += 2 << i, u = t[u][i], v = t[v][i];
  return u == v ? ans : ans + 2;
}
int main() {
  for (cin >> n, i = 2; i <= n; i++) cin >> t[i][0];
  for (j = t[1][0] = 1; j <= 20; j++)
    for (i = 1; i <= n; i++) t[i][j] = t[t[i][j - 1]][j - 1];
  for (i = 2, deep[1] = 1; i <= n; i++) dfs(i);
  for (ans = 0, u = v = 1, i = 2; i <= n; i++) {
    if ((j = len(u, i)) > ans) ans = j, v = i;
    if ((j = len(v, i)) > ans) ans = j, u = i;
    cout << ans << "\n";
  }
  return 0;
}
