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 _dbg(string) { cout << endl; }
template <class H, class... T>
void _dbg(string s, H h, T... t) {
  int l = s.find(',');
  cout << s.substr(0, l) << " = " << h << ", ";
  _dbg(s.substr(l + 1), t...);
}
template <class T, class U>
ostream& operator<<(ostream& o, const pair<T, U>& p) {
  o << "(" << p.first << "," << p.second << ")";
  return o;
}
template <class T>
ostream& operator<<(ostream& o, const vector<T>& v) {
  o << "[";
  for (T t : v) {
    o << t << ",";
  }
  o << "]";
  return o;
}
vector<int> tree[200010];
class LCA {
 private:
  int n, ln;

 public:
  vector<vector<int> > parent;
  vector<int> depth;
  LCA(int _n) : n(_n), depth(_n) {
    ln = 0;
    while (n > (1 << ln)) ln++;
    parent = vector<vector<int> >(ln, vector<int>(n));
  }
  void dfs(int v, int p, int d) {
    parent[0][v] = p;
    depth[v] = d;
    for (int i = (int)(0); i < (int)(tree[v].size()); i++)
      if (tree[v][i] != p) dfs(tree[v][i], v, d + 1);
  }
  void init(int root) {
    dfs(root, -1, 0);
    for (int k = 0; k + 1 < ln; k++) {
      for (int v = 0; v < n; v++) {
        if (parent[k][v] < 0)
          parent[k + 1][v] = -1;
        else
          parent[k + 1][v] = parent[k][parent[k][v]];
      }
    }
  }
  int query(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < ln; k++) {
      if ((depth[v] - depth[u]) >> k & 1) v = parent[k][v];
    }
    if (u == v) return u;
    for (int k = ln - 1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
};
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = (int)(0); i < (int)(n - 1); i++) {
    scanf("%d", &a[i]);
    a[i]--;
    tree[i + 1].push_back((a[i]));
    tree[a[i]].push_back((i + 1));
  }
  LCA lca(n);
  lca.init(0);
  int v1 = 0, v2 = 0;
  int ans = 0;
  auto dist = [&](int p, int q) {
    int pp = lca.query(p, q);
    return lca.depth[p] + lca.depth[q] - 2 * lca.depth[pp];
  };
  for (int i = (int)(0); i < (int)(n - 1); i++) {
    int d1 = dist(i + 1, v1);
    int d2 = dist(i + 1, v2);
    if (d1 > ans && d1 >= d2) {
      v2 = i + 1;
      ans = d1;
    } else if (d2 > ans) {
      v1 = i + 1;
      ans = d2;
    }
    printf("%d%c", ans, " \n"[i == n - 2]);
  }
  return 0;
}
