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;
const double eps = 0.000000000000001;
string convertstring(long long n) {
  stringstream ss;
  ss << n;
  return ss.str();
}
long long n, lev[300005], dp[300005][19 + 5], st[300005], en[300005], t;
vector<long long> g[300005];
void dfs(long long src, long long par) {
  st[src] = ++t;
  lev[src] = lev[par] + 1;
  dp[src][0] = par;
  for (long long i = 1; (1 << i) <= lev[src]; ++i)
    dp[src][i] = dp[dp[src][i - 1]][i - 1];
  for (long long i = 0; i < g[src].size(); ++i) {
    if (g[src][i] != par) dfs(g[src][i], src);
  }
  en[src] = ++t;
}
long long get_par(long long node, long long x) {
  for (long long i = 0; (1 << i) <= x; ++i) {
    if (x & (1 << i)) node = dp[node][i];
  }
  return node;
}
long long lca(long long u, long long v) {
  if (lev[u] < lev[v]) swap(u, v);
  long long diff = lev[u] - lev[v];
  long long xx = 0;
  u = get_par(u, diff);
  if (u == v) return u;
  for (long long i = 19; i >= 0; --i) {
    if (dp[u][i] != dp[v][i]) {
      u = dp[u][i];
      v = dp[v][i];
    }
  }
  return dp[u][0];
}
long long dis(long long u, long long v) {
  return lev[u] + lev[v] - 2 * lev[lca(u, v)];
}
long long get_closer(long long u, long long v) {
  assert(u != v);
  if (st[v] >= st[u] && en[v] <= en[u]) {
    long long x = dis(u, v);
    return get_par(v, x - 1);
  }
  return dp[u][0];
}
struct data {
  long long dis, count;
};
data tree[300005 << 3];
long long lazy[300005 << 3];
void aggregate(long long node) { tree[node].dis += lazy[node]; }
void push(long long node) {
  lazy[2 * node] += lazy[node];
  lazy[2 * node + 1] += lazy[node];
  lazy[node] = 0;
}
void change(long long node, long long st, long long en, long long qst,
            long long qen, long long val, long long val2) {
  if (lazy[node]) {
    aggregate(node);
    if (st != en) push(node);
    lazy[node] = 0;
  }
  if (qst > en || qen < st || st > en) return;
  if (st >= qst && en <= qen) {
    tree[node].dis = val;
    tree[node].count = val2;
    return;
  }
  long long mid = st + en >> 1;
  change(2 * node, st, mid, qst, qen, val, val2);
  change(2 * node + 1, mid + 1, en, qst, qen, val, val2);
  data d1 = tree[2 * node], d2 = tree[2 * node + 1];
  if (d1.dis > d2.dis)
    tree[node] = d1;
  else if (d1.dis < d2.dis)
    tree[node] = d2;
  else
    tree[node] = (data){d1.dis, d1.count + d2.count};
}
void update(long long node, long long st, long long en, long long qst,
            long long qen, long long val) {
  if (lazy[node]) {
    aggregate(node);
    if (st != en) push(node);
    lazy[node] = 0;
  }
  if (qst > en || qen < st || st > en) return;
  if (st >= qst && en <= qen) {
    lazy[node] += val;
    aggregate(node);
    if (st != en) push(node);
    lazy[node] = 0;
    return;
  }
  long long mid = st + en >> 1;
  update(2 * node, st, mid, qst, qen, val);
  update(2 * node + 1, mid + 1, en, qst, qen, val);
  data d1 = tree[2 * node], d2 = tree[2 * node + 1];
  if (d1.dis > d2.dis)
    tree[node] = d1;
  else if (d1.dis < d2.dis)
    tree[node] = d2;
  else
    tree[node] = (data){d1.dis, d1.count + d2.count};
}
data query(long long node, long long st, long long en, long long qst,
           long long qen) {
  if (qst > en || qen < st || st > en) return (data){-1000000001, 0};
  if (lazy[node]) {
    aggregate(node);
    if (st != en) push(node);
    lazy[node] = 0;
  }
  if (st >= qst && en <= qen) return tree[node];
  long long mid = st + en >> 1;
  data d1 = query(2 * node, st, mid, qst, qen);
  data d2 = query(2 * node + 1, mid + 1, en, qst, qen);
  if (d1.dis > d2.dis)
    return d1;
  else if (d1.dis < d2.dis)
    return d2;
  return (data){d1.dis, d1.count + d2.count};
}
int main() {
  long long i, l = 1, r = 1, dia = 0;
  vector<long long> center;
  center.push_back(1);
  long long m;
  scanf("%lld", &m);
  ;
  for (i = 1; i <= m; ++i) {
    long long x;
    scanf("%lld", &x);
    ;
    g[x].push_back(i + 1);
    g[i + 1].push_back(x);
  }
  for (i = 0; i < 300005 << 2; ++i)
    tree[i].dis = -1000000001, tree[i].count = 0;
  n = m + 1;
  dfs(1, 0);
  change(1, 1, t, st[1], st[1], 0, 1);
  change(1, 1, t, en[1], en[1], 0, 1);
  for (long long cur = 2; cur <= n; ++cur) {
    bool f = 0;
    long long diss;
    if (dia & 1)
      diss = min(dis(center[0], cur), dis(center[1], cur));
    else
      diss = dis(center[0], cur);
    change(1, 1, t, st[cur], st[cur], diss, 1);
    change(1, 1, t, en[cur], en[cur], diss, 1);
    if (dis(l, cur) > dia) {
      r = cur;
      dia++;
      f = 1;
    } else if (dis(r, cur) > dia) {
      l = cur;
      dia++;
      f = 1;
    }
    if (f) {
      if (dia & 1) {
        center.push_back(get_closer(center[0], cur));
        if (lev[center[1]] < lev[center[0]]) {
          update(1, 1, t, st[1], en[1], -1);
          update(1, 1, t, st[center[0]], en[center[0]], 1);
        } else {
          update(1, 1, t, st[center[1]], en[center[1]], -1);
        }
      } else {
        long long rem;
        if (dis(center[0], cur) > dis(center[1], cur))
          rem = 0;
        else
          rem = 1;
        if (lev[center[rem]] < lev[center[!rem]]) {
          update(1, 1, t, st[1], en[1], 1);
          update(1, 1, t, st[center[!rem]], en[center[!rem]], -1);
        } else {
          update(1, 1, t, st[center[rem]], en[center[rem]], 1);
        }
        center.erase(center.begin() + rem);
      }
    }
    printf("%lld\n", query(1, 1, t, st[1], en[1]).count / 2);
  }
  return 0;
}
