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 maxN = 1e6, maxLOG = 21;
vector<vector<int>> tree;
int up[maxN][maxLOG + 1];
vector<int> time_in, time_out, d;
int time_ = 0;
void dfs(int v, int p, int h) {
  time_in[v] = time_++;
  d[v] = h;
  up[v][0] = p;
  for (int l = 1; l <= maxLOG; l++) up[v][l] = up[up[v][l - 1]][l - 1];
  for (auto to : tree[v])
    if (to != p) dfs(to, v, h + 1);
  time_out[v] = time_++;
}
bool isAncestor(int v, int u) {
  if (time_in[v] <= time_in[u] && time_out[v] >= time_out[u]) return true;
  return false;
}
int lca(int v, int u) {
  if (isAncestor(v, u)) return v;
  for (int l = maxLOG - 1; l >= 0; l--) {
    int v_now = up[v][l];
    if (!isAncestor(v_now, u)) v = v_now;
  }
  return up[v][0];
}
int main() {
  int n;
  cin >> n;
  tree.resize(n);
  time_in.resize(n);
  time_out.resize(n);
  d.resize(n);
  vector<int> q(n);
  for (int i = 0; i < n - 1; i++) {
    int a;
    cin >> a;
    tree[i + 1].push_back(a - 1);
    tree[a - 1].push_back(i + 1);
    q[i] = i + 1;
  }
  dfs(0, 0, 0);
  int v1 = 0, v2 = 0;
  for (int i = 0; i < n - 1; i++) {
    int v = q[i];
    int lca1 = lca(v1, v2), lca2 = lca(v1, v), lca3 = lca(v2, v);
    int len1 = abs(2 * d[lca1] - d[v1] - d[v2]),
        len2 = abs(2 * d[lca2] - d[v1] - d[v]),
        len3 = abs(2 * d[lca3] - d[v2] - d[v]);
    if (max(len1, max(len2, len3)) == len2) {
      v2 = v;
      cout << len2 << " ";
    } else if (max(len1, max(len2, len3)) == len3) {
      v1 = v;
      cout << len3 << " ";
    } else
      cout << len1 << " ";
  }
}
