FJ Loves Rotations

Bác John có một mảng $A$ gồm $N$ số nguyên, đánh số từ $1$ đến $N$. Bác chọn trước một vị trí $j$ và ghi lại giá trị $A_j$ đang đứng ở đó.

Sau đó, mỗi bước bác dịch vòng cả mảng sang trái hoặc sang phải một ô, rồi ghi lại giá trị mới đang đứng ở vị trí $j$. Dịch vòng nghĩa là phần tử bị đẩy ra khỏi một đầu sẽ quay lại ở đầu kia.

Bác muốn ghi được tất cả các giá trị phân biệt có trong mảng. Với mỗi vị trí $j$ từ $1$ đến $N$, hãy tính số bước dịch ít nhất cần thực hiện.

Dữ liệu vào

• Dòng $1$: số nguyên $N$.
• Dòng $2$: $N$ số nguyên $A_1,A_2,\dots ,A_N$.

Dữ liệu ra

Một dòng gồm $N$ số nguyên cách nhau bởi dấu cách, số thứ $j$ là đáp án ứng với vị trí $j$.

Ràng buộc

• $1\le N\le 5\times {10}^5$
• $1\le A_i\le N$

Ví dụ