Farmer John has an array A containing N integers (1≤N≤5⋅105,1≤Ai≤N). He picks his favorite index j and take out a sheet of paper with only Aj written on it. He can then perform the following operation some number of times:
Cyclically shift all elements in A one spot to the left or one spot to the right. Then, write down Aj on a piece of paper.
Let S denote the set of distinct integers that occur in A. Farmer John wonders what the minimum number of operations he must perform is so that the paper contains all integers that appear in S.
Since it is unclear what FJ's favorite index is, output the answer for all possible favorite indices 1≤j≤N. Note for each index, A is reset to its original form before performing any operations.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The following line contains A1,A2,…,AN.
OUTPUT FORMAT (print output to the terminal / stdout):
Output N space-separated integers, where the i'th integer is the answer for his favorite index j=i.
SAMPLE INPUT:
6
1 2 3 1 3 4
SAMPLE OUTPUT:
4 3 3 4 3 3
The distinct numbers are S={1,2,3,4}. Suppose Farmer John’s favorite index is j=1. He starts off with A1=1 written on a piece of paper. We can track the array A after each cyclic shift Farmer John makes.
Cyclic shift right: FJ writes down A1=4.
4 1 2 3 1 3
Cyclic shift left: FJ writes down A1=1 again.
1 2 3 1 3 4
Cyclic shift left: FJ writes down A1=2.
2 3 1 3 4 1
Cyclic shift left: FJ writes down A1=3.
3 1 3 4 1 2
At this point, Farmer John has written down every number in S using 4 operations.
SAMPLE INPUT:
12
1 1 2 1 1 3 1 1 4 1 1 1
SAMPLE OUTPUT:
8 7 6 7 8 9 8 7 6 7 8 9
SCORING:
Inputs 3-5: N≤500
Inputs 6-8: N≤104
Inputs 9-17: No additional constraints.
Problem credits: Chongtian Ma
历年学员USACO获奖战绩一览
USACO 历年战绩
2026赛季战绩
- 5位铂金级
- 22位金级
- 25位银级
2024–2025赛季战绩
翰林考点及辅导学生
- 5位铂金级
- 25位金级
- 38位银级
2023–2024赛季战绩
- 8位铂金级
- 32位金级
- 37位银级
2022–2023赛季战绩
- 10位铂金级
- 29位金级
- 71位银级
篇幅有限,仅展示部分年份战绩。
