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
输入 #1
6
1 2 3 1 3 4输出 #1
4 3 3 4 3 3输入输出样例 #2
输入 #2
12
1 1 2 1 1 3 1 1 4 1 1 1输出 #2
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 完成