爆了(boom)

题目描述

有 $n$ 个盒子，每个盒子里有一个炸弹。第 $i$ 个盒子里的炸弹一旦被引爆，会把第 $p_i$ 个盒子的炸弹也引爆。注意这个操作可以连锁发生。

一个盒子里的炸弹引爆后就不会继续引爆了。

Alice 接下来会做 $n$ 次操作，第 $i$ 次操作会尝试引爆第 $i$ 个盒子里的炸弹。如果第 $i$ 个盒子的炸弹已经被引爆了，则跳过。

你需要在每次操作后，输出未被引爆的炸弹数量。

输入格式

第一行一个自然数 $n$ 。

接下来一行 $n$ 个自然数 $p_i$ 。

输出格式

输出一行 $n$ 个自然数，第 $i$ 个数表示第 $i$ 次尝试后的结果。

样例输入

4
2 1 3 3

样例输出

2 2 1 0

数据范围

对于 $30\%$ 的数据，$n\leq 10$

对于 $60\%$ 的数据，$n\leq 1000$

对于 $100\%$ 的数据，$1\leq p_i\leq n\leq 10^5$

时间限制 : 1000 ms

空间限制 : 1024 MB