说明

农夫约翰有一个包含 $N$ 个整数的数组 $A$（$1 \leq N \leq 5 \cdot 10^5$，$1 \leq A_i \leq N$）。他选择他最喜欢的下标 $j$，并拿出一张只写有 $A_j$ 的纸。然后他可以执行以下操作若干次：

• 将 $A$ 中的所有元素循环左移或循环右移一个位置。然后，在纸上写下 $A_j$。

设 $S$ 表示 $A$ 中出现的不同整数构成的集合。农夫约翰想知道，他至少需要执行多少次操作，才能使得纸上包含 $S$ 中的所有整数。

由于不清楚农夫约翰最喜欢的下标是哪个，请对所有可能的下标 $1 \leq j \leq N$ 输出答案。注意，对于每个下标，$A$ 在执行任何操作前都会被重置为初始形式。

输入格式

第一行包含 $N$。

接下来一行包含 $A_1, A_2, \ldots, A_N$。

输出格式

输出 $N$ 个由空格分隔的整数，其中第 $i$ 个整数对应最喜欢的下标 $j = i$ 时的答案。

6
1 2 3 1 3 4

4 3 3 4 3 3

12
1 1 2 1 1 3 1 1 4 1 1 1

8 7 6 7 8 9 8 7 6 7 8 9

提示

样例 1 解释

不同的数字是 $S = \{ 1, 2, 3, 4 \}$。假设农夫约翰最喜欢的下标是 $j=1$。他开始时纸上写有 $A_1=1$。我们可以跟踪农夫约翰每次循环移位后的数组 $A$。

• 循环右移：农夫约翰写下 $A_1 = 4$。此时数组为 4 1 2 3 1 3。
• 循环左移：农夫约翰再次写下 $A_1 = 1$。此时数组为 1 2 3 1 3 4。
• 循环左移：农夫约翰写下 $A_1 = 2$。此时数组为 2 3 1 3 4 1。
• 循环左移：农夫约翰写下 $A_1 = 3$。此时数组为 3 1 3 4 1 2。

此时，农夫约翰已经通过 4 次操作写下了 $S$ 中的每个数字。

评分

• 输入 3-5：$N \leq 500$
• 输入 6-8：$N \leq 10^4$
• 输入 9-17：无额外约束。

翻译由 DeepSeek 完成