문제

우진이는 $N$개의 정수가 담긴 수열 $A$를 가지고 있다. ($1 \le N \le 5 \cdot 10^5$; $1 \le A_i \le N$) 우진이는 자신이 좋아하는 인덱스 $j$를 하나 고른 뒤, 종이에 $A_j$를 적는다. 그 후, 우진이는 아래 연산을 원하는 만큼 수행할 수 있다.

• 수열 $A$의 모든 원소를 왼쪽 또는 오른쪽으로 한 칸씩 순환 이동(cyclically shift)시킨다. 그 후, 종이에 현재 위치 $j$에 있는 원소 $A_j$를 적는다.

$S$를 수열 $A$에 포함된 서로 다른 정수들의 집합이라고 하자. 우진이는 종이에 적힌 숫자들에 $S$의 모든 원소가 적어도 한 번씩 포함되도록 하기 위해 필요한 최소 연산 횟수를 구하고자 한다.

우진이가 선택할 수 있는 모든 가능한 인덱스 $1 \le j \le N$에 대하여 각각의 답을 구하시오. 각 인덱스에 대해 문제를 풀 때마다 수열 $A$는 처음 상태로 초기화된다.

입력

첫째 줄에 $N$이 주어진다. ($1 \le N \le 5 \cdot 10^5$)

둘째 줄에 수열의 원소 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어진다. ($1 \le A_i \le N$)

출력

$N$개의 정수를 공백으로 구분하여 출력한다. $i$번째 정수는 좋아하는 인덱스가 $j = i$일 때의 최소 연산 횟수이다.

예제 입력 1

6
1 2 3 1 3 4

예제 출력 1

4 3 3 4 3 3

예제 입력 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