FJ Loves Rotations

Bác John có một mảng $A$ gồm $N$ số nguyên. Bác chọn một vị trí yêu thích $j$ và ghi lại giá trị $A_j$.

Bác có thể thực hiện phép dịch vòng mảng sang trái hoặc phải (cyclic shift). Sau mỗi phép dịch, bác ghi lại giá trị mới tại vị trí $j$. Mục tiêu là thu thập tất cả các giá trị phân biệt có trong mảng.

Hãy tìm số phép dịch tối thiểu cần thực hiện để thu thập được tất cả các giá trị phân biệt, với mỗi vị trí $j$ từ $1$ đ��n $N$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$ ($1\le N\le 5\times {10}^5$).
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\dots ,A_N$ ($1\le A_i\le N$).

Dữ liệu ra

In $N$ số nguyên cách nhau b��i dấu cách, số thứ $i$ là đáp án khi $j=i$.

Ràng buộc

• $1\le N\le 5\times {10}^5$
• $1\le A_i\le N$
• Input 3-5: $N\le 500$
• Input 6-8: $N\le {10}^4$

Ví dụ