USACO

USACO 2026 Second Contest, Silver

Problem 3. Farmer John Loves Rotations

Contest has ended.

Log in to allow submissions in analysis mode

Farmer John has an array $A$ containing $N$ integers ($1 \leq N \leq 5 \cdot 10^5, 1 \leq A_i \leq N$). He picks his favorite index $j$ and take out a sheet of paper with only $A_j$ 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 $A_j$ 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 \leq j \leq 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 $A_1, A_2, \ldots, A_N$.

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 $A_1=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 $A_1 = 4$.
```
 4 1 2 3 1 3 
```
Cyclic shift left: FJ writes down $A_1 = 1$ again.
```
 1 2 3 1 3 4 
```
Cyclic shift left: FJ writes down $A_1 = 2$.
```
 2 3 1 3 4 1 
```
Cyclic shift left: FJ writes down $A_1 = 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\le 500$
Inputs 6-8: $N\le 10^4$
Inputs 9-17: No additional constraints.

Problem credits: Chongtian Ma

Contest has ended. No further submissions allowed.