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;
template <class T>
ostream& operator<<(ostream& os, vector<T> V) {
  for (auto v : V) os << v << " ";
  return cout << "";
}
template <class T>
ostream& operator<<(ostream& os, set<T> S) {
  for (auto s : S) os << s << " ";
  return cout << "";
}
template <class L, class R>
ostream& operator<<(ostream& os, pair<L, R> P) {
  return os << P.first << " " << P.second;
}
const long long mod = 1e9 + 7;
long long inv(long long i) {
  if (i == 1) return 1;
  return (mod - ((mod / i) * inv(mod % i)) % mod) % mod;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b, b % a);
}
vector<vector<int>> adj;
vector<bool> vis;
int n, l;
int timer;
vector<int> tin, tout, dis;
vector<vector<int>> up;
void dfs(int v, int p, int d = 0) {
  dis[v] = d;
  tin[v] = ++timer;
  up[v][0] = p;
  for (int i = 1; i <= l; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
  for (int u : adj[v]) {
    if (u != p) dfs(u, v, d + 1);
  }
  tout[v] = ++timer;
}
bool is_ancestor(int u, int v) {
  return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
  if (is_ancestor(u, v)) return u;
  if (is_ancestor(v, u)) return v;
  for (int i = l; i >= 0; --i) {
    if (!is_ancestor(up[u][i], v)) u = up[u][i];
  }
  return up[u][0];
}
void preprocess(int root) {
  tin.resize(n);
  tout.resize(n);
  timer = 0;
  l = ceil(log2(n));
  up.assign(n, vector<int>(l + 1));
  dis.assign(n, 0);
  dfs(root, root);
}
int dist(int u, int v) { return dis[u] + dis[v] - 2 * dis[lca(u, v)]; }
int main() {
  int i, p;
  cin >> n;
  adj.assign(n + 1, {});
  for (i = 2; i <= n; i++) {
    cin >> p;
    adj[i].push_back(p);
    adj[p].push_back(i);
  }
  n++;
  preprocess(1);
  int u = 1, v = 2, dia = 1;
  cout << (1) << " ";
  for (i = 3; i < n; i++) {
    int disiu = dist(i, u), disiv = dist(i, v);
    if (disiu > dia and disiu > disiv) {
      dia = disiu;
      v = i;
    } else if (disiv > dia) {
      dia = disiv;
      u = i;
    }
    cout << (dia) << " ";
  }
}
