Farmer John Loves Rotations

Farmer John has an array $A$ containing $N$ integers ( $1 \leq N \leq 5 \cdot 1 0^{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.

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.

SCORING:

Inputs 3-5: $N \leq 500$
Inputs 6-8: $N \leq 1 0^{4}$
Inputs 9-17: No additional constraints.

Problem credits: Chongtian Ma

Source: USA Computing Olympiad.

Input Format

The first line contains $N$ .

The following line contains $A_{1}, A_{2}, \dots, A_{N}$ .

Output Format

Output $N$ space-separated integers, where the $i$ 'th integer is the answer for his favorite index $j = i$ .

Sample Input 1

6 1 2 3 1 3 4

Sample Output 1

4 3 3 4 3 3

Sample Input 2

12 1 1 2 1 1 3 1 1 4 1 1 1

Sample Output 2

8 7 6 7 8 9 8 7 6 7 8 9

Submit

Language