← 返回题目列表

Codeforces · 1032/G

G. 喋喋不休

中文机器翻译题面 查看原题

有 $$$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