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;
void init() {
  ios::sync_with_stdio(0);
  cin.tie(0);
}
const int INF = 2147483647;
int height[400005];
int val[800005];
int lc[800005];
int rc[800005];
int cnt = -1;
vector<vector<int> > connection;
int buildST(int l, int r) {
  int cur = ++cnt;
  if (l == r)
    val[cur] = height[l];
  else {
    int m = (l + r) / 2;
    lc[cur] = buildST(l, m);
    rc[cur] = buildST(m + 1, r);
    val[cur] = min(val[lc[cur]], val[rc[cur]]);
  }
  return cur;
}
int LCA(int ql, int qr, int l, int r, int t) {
  if (ql > r || l > qr) return INF;
  if (ql <= l && r <= qr) return val[t];
  int m = (l + r) / 2;
  return min(LCA(ql, qr, l, m, lc[t]), LCA(ql, qr, m + 1, r, rc[t]));
}
int idx = 0;
bool used[200005];
int vertexHeight[200005];
int LCAPos[200005];
void buildLCA(int root, int h) {
  used[root] = true;
  height[idx] = h;
  vertexHeight[root] = h;
  LCAPos[root] = idx;
  idx++;
  for (auto i : connection[root]) {
    buildLCA(i, h + 1);
    height[idx] = h;
    idx++;
  }
}
int dist(int a, int b, int nodes) {
  if (LCAPos[a] > LCAPos[b]) swap(a, b);
  int lca = LCA(LCAPos[a], LCAPos[b], 0, nodes, 0);
  return vertexHeight[a] + vertexHeight[b] - lca - lca;
}
void connect(int a, int b) { connection[a].push_back(b); }
int arr[200005];
void input(int n) {
  vector<int> empty;
  for (int i = 0; i <= n + 1; i++) connection.push_back(empty);
  for (int i = 2; i <= n + 1; i++) {
    cin >> arr[i];
    connect(arr[i], i);
  }
}
int main() {
  init();
  int q;
  cin >> q;
  input(q - 1);
  buildLCA(1, 1);
  buildST(0, q * 2 - 1);
  int u = 1, v = 1;
  for (int i = 2; i <= q; i++) {
    int a, b, c;
    a = dist(u, v, 2 * q - 1);
    b = dist(u, i, 2 * q - 1);
    c = dist(i, v, 2 * q - 1);
    int Max = max(max(a, b), c);
    cout << Max << " ";
    if (Max == b)
      v = i;
    else if (Max == c)
      u = i;
  }
  cout << "\n";
}
