Nikita plays a new computer game. There are m levels in this game. In the beginning of each level a new class appears in the game; this class is a child-class of the class yi (and yi is called parent-class for this new class). Thus, the classes form a tree. Initially there is only one class with index 1.

Changing the class to its neighbour (child-class or parent-class) in the tree costs 1 coin. You can not change the class back. The cost of changing the class a to the class b is equal to the total cost of class changes on the path from a to b in the class tree.

Suppose that at i -th level the maximum cost of changing one class to another is x. For each level output the number of classes such that for each of these classes there exists some other class y, and the distance from this class to y is exactly x.

Input

First line contains one integer number m — number of queries (1 ≤ m ≤ 3·105).

Next m lines contain description of queries. i -th line (1 ≤ i ≤ m) describes the i -th level and contains an integer yi — the index of the parent-class of class with index i + 1 (1 ≤ yi ≤ i). 

Output

Suppose that at i -th level the maximum cost of changing one class to another is x. For each level output the number of classes such that for each of these classes there exists some other class y, and the distance from this class to y is exactly x.

Examples

Input

4
1
1
2
1


Output

2
2
2
3


Input

4
1
1
2
3


Output

2
2
2
2
#include <bits/stdc++.h>
using namespace std;
namespace baseFastio {
template <typename Int>
inline Int read() {
  Int flag = 1;
  char c = getchar();
  while ((!isdigit(c)) && c != '-' && c != EOF) c = getchar();
  if (c == '-') flag = -1, c = getchar();
  Int init = c & 15;
  while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
  return init * flag;
}
template <typename Int>
inline Int read(char& c) {
  Int flag = 1;
  c = getchar();
  while ((!isdigit(c)) && c != '-' && c != EOF) c = getchar();
  if (c == '-') flag = -1, c = getchar();
  Int init = c & 15;
  while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
  return init * flag;
}
template <typename Int>
inline void write(Int x) {
  if (x < 0) putchar('-'), x = ~x + 1;
  if (x > 9) write(x / 10);
  putchar((x % 10) | 48);
}
template <typename Int>
inline void write(Int x, char nextch) {
  write(x);
  putchar(nextch);
}
}  // namespace baseFastio
namespace Fastio {
enum io_flags { ignore_int = 1 << 0 };
struct Reader {
  char endch;
  Reader() { endch = '\0'; }
  template <typename Int>
  Int operator()() {
    return baseFastio::read<Int>(endch);
    ;
  }
  Reader& operator>>(io_flags f) {
    if (f == ignore_int) baseFastio::read<int>();
    return *this;
  }
  template <typename Int>
  Reader& operator>>(Int& i) {
    i = baseFastio::read<Int>(endch);
    return *this;
  }
  template <typename Int>
  inline Int get_int() {
    return baseFastio::read<Int>();
  }
  inline char get_nxt() { return endch; }
} read;
struct Writer {
  Writer& operator<<(const char* ch) {
    while (*ch) putchar(*(ch++));
    return *this;
  }
  Writer& operator<<(const char ch) {
    putchar(ch);
    return *this;
  }
  template <typename Int>
  Writer& operator<<(const Int i) {
    baseFastio::write(i);
    return *this;
  }
} write;
}  // namespace Fastio
using namespace Fastio;
const int N = 3e5 + 7, INT_MIN_DIV_3 = INT_MIN / 3;
map<int, int> dis[N], disf[N];
map<int, int>::iterator it;
namespace against_cpp11 {
int n, y[N], diam[N];
int LCA_fa[N][20], dep[N];
vector<int> G[N];
void update_father_list(int u) {
  for (int i = 0; i < 19; i++) LCA_fa[u][i + 1] = LCA_fa[LCA_fa[u][i]][i];
}
void jump(int& u, int delta) {
  for (int k = 0; k < 20; k++)
    if (delta & (1 << k)) u = LCA_fa[u][k];
}
int LCA(int u, int v) {
  if (dep[u] > dep[v])
    jump(u, dep[u] - dep[v]);
  else if (dep[u] < dep[v])
    jump(v, dep[v] - dep[u]);
  if (u == v) return u;
  for (int k = 19; LCA_fa[u][0] != LCA_fa[v][0]; k--)
    if (LCA_fa[u][k] != LCA_fa[v][k]) {
      u = LCA_fa[u][k];
      v = LCA_fa[v][k];
    }
  return LCA_fa[u][0];
}
int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[LCA(u, v)]; }
vector<int> s1, s2;
signed main() {
  read >> n;
  s1.push_back(1);
  n++;
  for (int i = 2, d1, d2, maxd = 0; i <= n; i++) {
    read >> y[i];
    LCA_fa[i][0] = y[i];
    update_father_list(i);
    dep[i] = dep[y[i]] + 1;
    G[y[i]].push_back(i);
    G[i].push_back(y[i]);
    d1 = s1.empty() ? 0 : dist(s1[0], i);
    d2 = s2.empty() ? 0 : dist(s2[0], i);
    if (d1 >= d2 && d1 > maxd) {
      maxd = d1;
      for (size_t j = 0; j < s2.size(); j++)
        if (dist(i, s2[j]) == maxd) s1.push_back(s2[j]);
      s2.clear();
      s2.push_back(i);
    } else if (d2 > d1 && d2 > maxd) {
      maxd = d2;
      for (size_t j = 0; j < s1.size(); j++)
        if (dist(i, s1[j]) == maxd) s2.push_back(s1[j]);
      s1.clear();
      s1.push_back(i);
    } else if (d1 == maxd) {
      s2.push_back(i);
    } else if (d2 == maxd) {
      s1.push_back(i);
    }
    write << s1.size() + s2.size() << '\n';
  }
  return 0;
}
}  // namespace against_cpp11
signed main() { return against_cpp11::main(); }
