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>
#pragma comment(linker, ”/ STACK : 256000000“)
using namespace std;
inline void fr(int &to) {
  char t = getchar();
  to ^= to;
  while (t > 47) {
    to = (to << 3) + (to << 1) + t - 48;
    t = getchar();
  }
}
void fw(const int &what) {
  if (what > 9) fw(what / 10);
  putchar(what % 10 + 48);
}
int n, r, anc[200010][25] = {};
int d1 = 1, d2 = 1, d = 0;
int T = 0, tin[200010], tout[200010];
vector<int> g[200010];
inline void lca_calc(int v, int p) {
  tin[v] = T++;
  anc[v][0] = p;
  for (int i = 1; i < 25; ++i) anc[v][i] = anc[anc[v][i - 1]][i - 1];
  for (auto &i : g[v]) lca_calc(i, v);
  tout[v] = T++;
}
inline int isupper(int a, int b) {
  return tin[a] <= tin[b] && tout[a] >= tout[b];
}
inline int line(int a, int b) {
  int k = 0;
  for (int i = 24; i >= 0; --i)
    if (isupper(a, anc[b][i]) && anc[b][i]) k += 1 << i, b = anc[b][i];
  return k;
}
inline int lca(const int &a, const int &b) {
  if (isupper(a, b)) return line(a, b);
  if (isupper(b, a)) return line(b, a);
  int k = a;
  for (int i = 24; i >= 0; --i)
    if (!isupper(anc[k][i], b) && anc[k][i]) k = anc[k][i];
  k = anc[k][0];
  return line(k, a) + line(k, b);
}
int main() {
  fr(n);
  for (int i = 2; i <= n; ++i) fr(r), g[r].push_back(i);
  lca_calc(1, 0);
  for (int i = 2; i <= n; ++i) {
    int now1 = lca(d1, i);
    int now2 = lca(d2, i);
    if (d < now1) d = now1, d2 = i;
    if (d < now2) d = now2, d1 = i;
    fw(d), putchar(' ');
  }
}
