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