题目描述

每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的$\red{N(1≤}$$\red{N≤}$$\red{100000)}$个牛棚里转悠，来采集糖果．

她们每走到一个未曾经过的牛棚，就会采集这个棚里的$\red{1}$颗糖果． 农场不大，所以约翰要想尽法子让奶牛们得到快乐．他给每一个牛棚设置了一个"后继牛棚"．牛棚$\red{i}$的后继牛棚是$\red{X_i}$．

他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去，就可以搜集到很多糖果．事实上这是一种有点欺骗意味的手段，来节约他的糖果． 第$\red{i}$只奶牛从牛棚$\red{i}$开始她的旅程．

请你计算，每一只奶牛可以采集到多少糖果．

输入格式

第$\red{1}$行输入$\red{N，}$之后一行一个整数表示牛棚$\red{i}$的后继牛棚$\red{Xi，}$共$\red{N}$行．

输出格式

共$\red{N}$行，一行一个整数表示一只奶牛可以采集的糖果数量．

样例

输入样例

4
1    
3
2
3

输出样例

1
2
2
3

提示

输入详细信息： 四个摊位。 $\red{*}$档位$\red{1}$将奶牛引导回档位$\red{1}$。 $\red{*}$档位$\red{2}$将奶牛引导到档位$\red{3}$ $\red{*}$档位$\red{3}$将奶牛引导到档位$\red{2}$ $\red{*}$档位$\red{4}$将奶牛引向档位$\red{3}$

奶牛$\red{1：}$从$\red{1}$开始，下一个是$\red{1}$。

参观摊位总数：$\red{1}$。

奶牛$\red{2：}$从$\red{2}$开始，下一个是$\red{3，}$下一个是$\red{2}$。

参观的摊位 总数：$\red{2}$个。

奶牛$\red{3：}$从$\red{3}$开始，下一个是$\red{2，}$下一个是$\red{3}$。

参观的摊位总数：$\red{2}$个。

奶牛$\red{4：}$从$\red{4}$开始，下一个 是$\red{3，}$下一个是$\red{2，}$下一个是$\red{3}$。

参观的摊位总数：$\red{3}$个。