Farmer John 有一个包含 $N$ 个整数的数组 $A$ ($1 \leq N \leq 5 \cdot 10^5, 1 \leq A_i \leq N$)。他选定了一个他最喜欢的下标 $j$，并在纸上写下 $A_j$。随后，他可以进行若干次以下操作：
- 将数组 $A$ 中的所有元素循环左移一位或右移一位。然后，在纸上写下当前的 $A_j$。
令 $S$ 为 $A$ 中出现的所有不同整数组成的集合。Farmer John 想知道，为了使纸上包含 $S$ 中的所有整数，他最少需要进行多少次操作。
由于不确定 FJ 最喜欢的下标是哪一个，请输出对于所有可能的下标 $1 \leq j \leq N$ 的答案。注意，对于每个下标，在进行任何操作之前，$A$ 都会重置为初始状态。
输入格式
第一行包含 $N$。
下一行包含 $A_1, A_2, \ldots, A_N$。
输出格式
输出 $N$ 个以空格分隔的整数，其中第 $i$ 个整数表示以 $j = i$ 作为他最喜欢的下标时的答案。
样例
输入 1
6 1 2 3 1 3 4
输出 1
4 3 3 4 3 3
说明 1
不同的数字集合为 $S = \{ 1, 2, 3, 4 \}$。假设 Farmer John 最喜欢的下标是 $j=1$。他开始时在纸上写下了 $A_1=1$。我们可以追踪 Farmer John 每次循环移位后的数组 $A$：
- 循环右移：FJ 写下 $A_1 = 4$。
4 1 2 3 1 3
- 循环左移：FJ 再次写下 $A_1 = 1$。
1 2 3 1 3 4
- 循环左移：FJ 写下 $A_1 = 2$。
2 3 1 3 4 1
- 循环左移：FJ 写下 $A_1 = 3$。
3 1 3 4 1 2
此时，Farmer John 通过 4 次操作写下了 $S$ 中的所有数字。
输入 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
子任务
- 测试点 3-5：$N\le 500$
- 测试点 6-8：$N\le 10^4$
- 测试点 9-17：无额外限制。
题目来源：Chongtian Ma