有 $$$n$$$ 鹦鹉围成一圈。每只鹦鹉在其他鹦鹉之间都有一定程度的尊重,即$$$r_i$$$。当尊重级别 $$$x$$$ 的鹦鹉开始喋喋不休时,$$$x$$$ 左右两侧的邻居会在 1 秒内开始重复相同的单词。然后,它们的邻居也开始重复,依此类推,直到所有的鸟儿都开始叽叽喳喳。
您将获得所有鹦鹉的尊重级别。对于每只鹦鹉,回答一个问题:如果这只鹦鹉开始喋喋不休,需要多少秒后所有其他鸟才会开始重复它?
输入
在输入的第一行中有一个整数 $$$n$$$,即鹦鹉的数量 ($$$1 \leq n \leq 10^5$$$)。
在输入的下一行中,有 $$$n$$$ 整数 $$$r_1$$$, ..., $$$r_n$$$,即鹦鹉在圆圈中排列顺序的尊重级别 ($$$1 \leq r_i \leq n$$$)。
输出
打印 $$$n$$$ 整数。如果第 $$$i$$$ 鹦鹉首先开始说话,则其中第 $$$i$$$ 应该等于所有鹦鹉开始喋喋不休所需的秒数。
示例
输入 #1
4 1 1 4 1
输出 #1
2 2 1 2
输入 #2
8 1 2 2 1 5 1 3 1
输出 #2
3 3 2 2 1 2 2 3