#include <bits/stdc++.h>
using namespace std;
const int INF = int(1e9), N = 1e6, M = 21;
int n, up[M][N], tin[N], tout[N], p[4 * N], timer;
pair<int, int> t[4 * N];
vector<int> g[N];
void push(int now)
{
if (p[now] == 0)
{
return;
}
t[now].first += p[now];
if (now * 2 + 2 < 4 * N)
{
p[now * 2 + 1] += p[now];
p[now * 2 + 2] += p[now];
}
p[now] = 0;
}
void update1(int now)
{
int l = now * 2 + 1;
int r = now * 2 + 2;
if (t[l].first > t[r].first)
{
t[now] = t[l];
}
else if (t[r].first > t[l].first)
{
t[now] = t[r];
}
else
{
t[now] = t[l];
t[now].second += t[r].second;
}
}
void change(int now, int l, int r, int pos, int val)
{
push(now);
if (l == r)
{
t[now] = {val, 1};
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
{
change(now * 2 + 1, l, mid, pos, val);
}
else
{
change(now * 2 + 2, mid + 1, r, pos, val);
}
push(now * 2 + 1);
push(now * 2 + 2);
update1(now);
}
void update(int now, int l, int r, int tl, int tr, int val)
{
if (tl > tr)
{
return;
}
push(now);
if (l == tl && r == tr)
{
p[now] += val;
push(now);
return;
}
int mid = (l + r) / 2;
update(now * 2 + 1, l, mid, tl, min(mid, tr), val);
update(now * 2 + 2, mid + 1, r, max(tl, mid + 1), tr, val);
push(now * 2 + 1);
push(now * 2 + 2);
update1(now);
}
void dfs(int v, int p = 0)
{
tin[v] = timer++;
up[0][v] = p;
for(int i = 1; i < M; i++)
{
up[i][v] = up[i - 1][up[i - 1][v]];
}
for(int i = 0; i < g[v].size(); i++)
{
int u = g[v][i];
if (u != p)
{
dfs(u, v);
}
}
tout[v] = timer++;
}
bool anc(int p, int v)
{
return tin[p] <= tin[v] && tout[v] <= tout[p];
}
int dist(int v1, int v2)
{
if (anc(v1, v2))
{
return 0;
}
int ans = 0;
for (int i = M - 1; i >= 0; i--)
{
if (!anc(up[i][v1], v2))
{
ans += (1 << i);
v1 = up[i][v1];
}
}
return ans + 1;
}
int lca(int v1, int v2)
{
for (int i = M - 1; i >= 0; i--)
{
if (!anc(up[i][v1], v2))
{
v1 = up[i][v1];
}
}
return v1;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
n++;
for(int i = 1; i < n; i++)
{
int x;
cin >> x;
x--;
g[i].push_back(x);
g[x].push_back(i);
}
for (int i = 0; i < N * 4; i++)
{
t[i] = {-INF, 0};
}
dfs(0);
pair<int, int> c = {0, -1};
change(0, 0, 2 * n - 1, tin[0], 0);
for(int i = 1; i < n; i++)
{
int cd = t[0].first;
int v = i;
int nd = dist(v, c.first) + dist(c.first, v);
if (c.second != -1)
{
int nd2 = dist(v, c.second) + dist(c.second, v);
if (nd2 < nd)
{
nd = nd2;
swap(c.first, c.second);
}
}
change(0, 0, 2 * n - 1, tin[v], nd);
if (nd > cd)
{
pair<int, int> nc;
if (c.second != -1)
{
nc = {c.first, -1};
if (anc(c.first, c.second))
{
update(0, 0, 2 * n - 1, tin[c.second], tout[c.second], 1);
}
else
{
if (c.first > 0)
{
update(0, 0, 2 * n - 1, 0, tin[c.first] - 1, 1);
}
if (c.first < 2 * n - 1)
{
update(0, 0, 2 * n - 1, tout[c.first] + 1, 2 * n - 1, 1);
}
}
}
else
{
if (anc(c.first, v))
{
nc = {lca(v, c.first), c.first};
}
else
{
nc = {up[0][c.first], c.first};
}
if (anc(nc.first, nc.second))
{
if (nc.second > 0)
{
update(0, 0, 2 * n - 1, 0, tin[nc.second] - 1, -1);
}
if (nc.second < 2 * n - 1)
{
update(0, 0, 2 * n - 1, tout[nc.second] + 1, 2 * n - 1, -1);
}
}
else
{
update(0, 0, 2 * n - 1, tin[nc.first], tout[nc.first], -1);
}
}
c = nc;
}
cout << t[0].second << "\n";
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IElORiA9IGludCgxZTkpLCBOID0gMWU2LCBNID0gMjE7CgppbnQgbiwgdXBbTV1bTl0sIHRpbltOXSwgdG91dFtOXSwgcFs0ICogTl0sIHRpbWVyOwpwYWlyPGludCwgaW50PiB0WzQgKiBOXTsKdmVjdG9yPGludD4gZ1tOXTsKCnZvaWQgcHVzaChpbnQgbm93KQp7CglpZiAocFtub3ddID09IDApCiAgICB7CgkJcmV0dXJuOwoJfQoJdFtub3ddLmZpcnN0ICs9IHBbbm93XTsKCWlmIChub3cgKiAyICsgMiA8IDQgKiBOKQoJewoJCXBbbm93ICogMiArIDFdICs9IHBbbm93XTsKCQlwW25vdyAqIDIgKyAyXSArPSBwW25vd107Cgl9CglwW25vd10gPSAwOwp9Cgp2b2lkIHVwZGF0ZTEoaW50IG5vdykKewoJaW50IGwgPSBub3cgKiAyICsgMTsKCWludCByID0gbm93ICogMiArIDI7CglpZiAodFtsXS5maXJzdCA+IHRbcl0uZmlyc3QpCiAgICB7CgkJdFtub3ddID0gdFtsXTsKCX0KCWVsc2UgaWYgKHRbcl0uZmlyc3QgPiB0W2xdLmZpcnN0KQogICAgewogICAgICAgIHRbbm93XSA9IHRbcl07CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgdFtub3ddID0gdFtsXTsKICAgICAgICB0W25vd10uc2Vjb25kICs9IHRbcl0uc2Vjb25kOwoJfQp9Cgp2b2lkIGNoYW5nZShpbnQgbm93LCBpbnQgbCwgaW50IHIsIGludCBwb3MsIGludCB2YWwpCnsKCXB1c2gobm93KTsKCWlmIChsID09IHIpCiAgICB7CgkJdFtub3ddID0ge3ZhbCwgMX07CgkJcmV0dXJuOwoJfQoJaW50IG1pZCA9IChsICsgcikgLyAyOwoJaWYgKHBvcyA8PSBtaWQpCgl7CgkJY2hhbmdlKG5vdyAqIDIgKyAxLCBsLCBtaWQsIHBvcywgdmFsKTsKCX0KCWVsc2UKICAgIHsKCQljaGFuZ2Uobm93ICogMiArIDIsIG1pZCArIDEsIHIsIHBvcywgdmFsKTsKCX0KCXB1c2gobm93ICogMiArIDEpOwoJcHVzaChub3cgKiAyICsgMik7Cgl1cGRhdGUxKG5vdyk7Cn0KCnZvaWQgdXBkYXRlKGludCBub3csIGludCBsLCBpbnQgciwgaW50IHRsLCBpbnQgdHIsIGludCB2YWwpCnsKICAgIGlmICh0bCA+IHRyKQogICAgewogICAgICAgIHJldHVybjsKICAgIH0KCXB1c2gobm93KTsKCWlmIChsID09IHRsICYmIHIgPT0gdHIpCiAgICB7CgkJcFtub3ddICs9IHZhbDsKCQlwdXNoKG5vdyk7CgkJcmV0dXJuOwoJfQoJaW50IG1pZCA9IChsICsgcikgLyAyOwoJdXBkYXRlKG5vdyAqIDIgKyAxLCBsLCBtaWQsIHRsLCBtaW4obWlkLCB0ciksIHZhbCk7Cgl1cGRhdGUobm93ICogMiArIDIsIG1pZCArIDEsIHIsIG1heCh0bCwgbWlkICsgMSksIHRyLCB2YWwpOwoJcHVzaChub3cgKiAyICsgMSk7CglwdXNoKG5vdyAqIDIgKyAyKTsKCXVwZGF0ZTEobm93KTsKfQoKdm9pZCBkZnMoaW50IHYsIGludCBwID0gMCkKewoJdGluW3ZdID0gdGltZXIrKzsKCXVwWzBdW3ZdID0gcDsKCWZvcihpbnQgaSA9IDE7IGkgPCBNOyBpKyspCgl7CiAgICAgICAgdXBbaV1bdl0gPSB1cFtpIC0gMV1bdXBbaSAtIDFdW3ZdXTsKICAgIH0KCWZvcihpbnQgaSA9IDA7IGkgPCBnW3ZdLnNpemUoKTsgaSsrKQoJewoJCWludCB1ID0gZ1t2XVtpXTsKCQlpZiAodSAhPSBwKQogICAgICAgIHsKCQkJZGZzKHUsIHYpOwoJCX0KCX0KCXRvdXRbdl0gPSB0aW1lcisrOwp9Cgpib29sIGFuYyhpbnQgcCwgaW50IHYpCnsKCXJldHVybiB0aW5bcF0gPD0gdGluW3ZdICYmIHRvdXRbdl0gPD0gdG91dFtwXTsKfQoKaW50IGRpc3QoaW50IHYxLCBpbnQgdjIpCnsKICAgIGlmIChhbmModjEsIHYyKSkKICAgIHsKIAkgICAgcmV0dXJuIDA7CiAgICB9CglpbnQgYW5zID0gMDsKCWZvciAoaW50IGkgPSBNIC0gMTsgaSA+PSAwOyBpLS0pCgl7CgkJaWYgKCFhbmModXBbaV1bdjFdLCB2MikpCgkJewoJCQlhbnMgKz0gKDEgPDwgaSk7CgkJCXYxID0gdXBbaV1bdjFdOwoJCX0KCX0KCXJldHVybiBhbnMgKyAxOwp9CgppbnQgbGNhKGludCB2MSwgaW50IHYyKQp7Cglmb3IgKGludCBpID0gTSAtIDE7IGkgPj0gMDsgaS0tKQoJewoJCWlmICghYW5jKHVwW2ldW3YxXSwgdjIpKQogICAgICAgIHsKCQkJdjEgPSB1cFtpXVt2MV07CgkJfQoJfQoJcmV0dXJuIHYxOwp9CgppbnQgbWFpbigpCnsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKDApOwogICAgY291dC50aWUoMCk7CiAgICBjaW4gPj4gbjsKICAgIG4rKzsKCWZvcihpbnQgaSA9IDE7IGkgPCBuOyBpKyspCgl7CgkJaW50IHg7CgkJY2luID4+IHg7CgkJeC0tOwoJCWdbaV0ucHVzaF9iYWNrKHgpOwoJCWdbeF0ucHVzaF9iYWNrKGkpOwoJfQoJZm9yIChpbnQgaSA9IDA7IGkgPCBOICogNDsgaSsrKQogICAgewogICAgICAgIHRbaV0gPSB7LUlORiwgMH07CiAgICB9CiAgICBkZnMoMCk7CglwYWlyPGludCwgaW50PiBjID0gezAsIC0xfTsKCWNoYW5nZSgwLCAwLCAyICogbiAtIDEsIHRpblswXSwgMCk7Cglmb3IoaW50IGkgPSAxOyBpIDwgbjsgaSsrKQoJewoJCWludCBjZCA9IHRbMF0uZmlyc3Q7CgkJaW50IHYgPSBpOwoJCWludCBuZCA9IGRpc3QodiwgYy5maXJzdCkgKyBkaXN0KGMuZmlyc3QsIHYpOwoJCWlmIChjLnNlY29uZCAhPSAtMSkKICAgICAgICB7CgkJCWludCBuZDIgPSBkaXN0KHYsIGMuc2Vjb25kKSArIGRpc3QoYy5zZWNvbmQsIHYpOwoJCQlpZiAobmQyIDwgbmQpCiAgICAgICAgICAgIHsKCQkJCW5kID0gbmQyOwoJCQkJc3dhcChjLmZpcnN0LCBjLnNlY29uZCk7CgkJCX0KCQl9CgkJY2hhbmdlKDAsIDAsIDIgKiBuIC0gMSwgdGluW3ZdLCBuZCk7CgkJaWYgKG5kID4gY2QpCiAgICAgICAgewogICAgICAgICAgICBwYWlyPGludCwgaW50PiBuYzsKICAgICAgICAgICAgaWYgKGMuc2Vjb25kICE9IC0xKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBuYyA9IHtjLmZpcnN0LCAtMX07CiAgICAgICAgICAgICAgICBpZiAoYW5jKGMuZmlyc3QsIGMuc2Vjb25kKSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICB1cGRhdGUoMCwgMCwgMiAqIG4gLSAxLCB0aW5bYy5zZWNvbmRdLCB0b3V0W2Muc2Vjb25kXSwgMSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYgKGMuZmlyc3QgPiAwKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgdXBkYXRlKDAsIDAsIDIgKiBuIC0gMSwgMCwgdGluW2MuZmlyc3RdIC0gMSwgMSk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGlmIChjLmZpcnN0IDwgMiAqIG4gLSAxKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgdXBkYXRlKDAsIDAsIDIgKiBuIC0gMSwgdG91dFtjLmZpcnN0XSArIDEsIDIgKiBuIC0gMSwgMSk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKGFuYyhjLmZpcnN0LCB2KSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBuYyA9IHtsY2EodiwgYy5maXJzdCksIGMuZmlyc3R9OwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIG5jID0ge3VwWzBdW2MuZmlyc3RdLCBjLmZpcnN0fTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGlmIChhbmMobmMuZmlyc3QsIG5jLnNlY29uZCkpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYgKG5jLnNlY29uZCA+IDApCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICB1cGRhdGUoMCwgMCwgMiAqIG4gLSAxLCAwLCB0aW5bbmMuc2Vjb25kXSAtIDEsIC0xKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgaWYgKG5jLnNlY29uZCA8IDIgKiBuIC0gMSkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHVwZGF0ZSgwLCAwLCAyICogbiAtIDEsIHRvdXRbbmMuc2Vjb25kXSArIDEsIDIgKiBuIC0gMSwgLTEpOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICB1cGRhdGUoMCwgMCwgMiAqIG4gLSAxLCB0aW5bbmMuZmlyc3RdLCB0b3V0W25jLmZpcnN0XSwgLTEpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgICAgIGMgPSBuYzsKICAgICAgICB9CiAgICAgICAgY291dCA8PCB0WzBdLnNlY29uZCA8PCAiXG4iOwoJfQogICAgcmV0dXJuIDA7Cn0=