Tại chợ JOI có \(K\) loại macaron. Một hộp gồm \(N\) chiếc được xếp thành một hàng; chiếc thứ \(i\) có loại \(A_i\).

Bitaro muốn phủ một tấm che lên nhiều nhất một đoạn liên tiếp để che các chiếc macaron trong đoạn đó. Nếu phủ từ vị trí \(l\) đến vị trí \(r\) (\(1\le l\le r\le N\)), độ dài tấm che là \(r-l+1\).

Bibako chỉ lấy macaron khi cả \(K\) loại đều còn nhìn thấy. Bitaro muốn ngăn Bibako lấy hộp bằng một tấm che ngắn nhất. Hãy tìm độ dài nhỏ nhất phải che. Nếu ngay từ đầu đã có ít nhất một loại không xuất hiện, không cần che gì cả.

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(N,K\). Dòng thứ hai gồm \(N\) số nguyên \(A_1,A_2,\ldots,A_N\).

Dữ liệu ra

In độ dài nhỏ nhất của tấm che. Nếu không cần che, in \(0\).

Ràng buộc

• \(1\le K\le N\le500000\).
• \(1\le A_i\le K\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

1. \(20\) điểm: \(N\le100\).
2. \(30\) điểm: \(K\le100\).
3. \(50\) điểm: không có ràng buộc thêm.

Ví dụ

7 3
1 3 2 3 1 2 3

4

7 4
1 3 4 4 1 3 1

0

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 1, bài Macaron.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.