Problem I: Making Pairs

Problem

本日、ついに完全招待制の高級レストラン「マイヅレストラン」がオープンした。新たな会員を招待する権利を持つのはこのレストランの会員のみで、最初、会員は会員番号0であるレストランのオーナーのみである。

マイヅレストランはその高級さ故、オープン初日から$N$日間しか開かれない。その期間中、毎日会員のうち誰か一人が、自分の友人を一人だけ新たに会員として招待する。$i$日目に招待された会員には会員番号$i$が割り当てられ、その会員は招待された日を含めそれ以降毎日来店する。

このレストランには二人用テーブルしか存在しないので、会員の人々はできるだけペアでテーブルを使用して食事をする。食事にはオーナーも参加するので、他の会員はオーナーとペアを組むこともできる。しかし、会員の人々は皆人見知りであり、自分を招待した友人か、自分が招待した友人としかペアを組みたがらない。各会員はもし友人とペアを組めなかった場合、一人寂しく食事をする。

$N$日間の各日について、友人どうしのペアの数が最大となるようにペアを組んだとき、いくつのペアができるか求めよ。

Input

入力は以下の形式で与えられる。

$N$
$p_1$
$p_2$
...
$p_N$

1行目にレストランが開かれる日数$N$が与えられる。
続く$N$行に、会員番号が$i$の会員を招待した会員の会員番号$p_i$が与えられる。

Constraints

入力は以下の条件を満たす。

• $1 \leq N \leq 5000$
• $0 \leq p_i \leq i-1$ ($1 \leq i \leq N$)
• $N$, $p_i$は整数

Output

出力は$N$行からなる。
$i$行目には、$i$日目に作ることのできる友人どうしのペアの最大数を出力する。 ($1 \leq i \leq N$)

Sample Input 1

3
0
0
2

Sample Output 1

1
1
2

Sample Input 2

5
0
1
2
3
4

Sample Output 2

1
1
2
2
3