FJ Loves Rotations

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq N \leq 5 \times 10^{5}$ ).
Dòng thứ hai chứa $N$ số nguyên $A_{1}, A_{2}, \dots, A_{N}$ ( $1 \leq A_{i} \leq 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 \leq N \leq 5 \times 10^{5}$
$1 \leq A_{i} \leq N$
Input 3-5: $N \leq 500$
Input 6-8: $N \leq 10^{4}$

Ví dụ

Input	Output	Giải thích
6 1 2 3 1 3 4	4 3 3 4 3 3	Có 4 giá trị phân biệt: 1,2,3,4. Với $j = 1$ : cần 4 phép dịch. Với $j = 2$ : cần 3 phép dịch (dịch phải 3 lần thu được tất cả).
12 1 1 2 1 1 3 1 1 4 1 1 1	8 7 6 7 8 9 8 7 6 7 8 9	Có 4 giá trị phân biệt. Tối ưu nhất bắt đầu từ vị trí 3 hoặc 9 (cần 6 phép).

Bình luận

Không có bình luận tại thời điểm này.