P15259 [USACO26JAN2] Farmer John Loves Rotations S

农夫约翰有一个包含 $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$ 时的答案。

#### 样例 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 完成