Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Nhờ đạt kết quả cao trong kỳ thi học sinh giỏi, Phát được mẹ thưởng một hộp bút màu rất đẹp. Hộp có ~n~ cây bút màu xếp thành hàng từ trái sang phải, cây thứ ~i~ ~(1 \le i \le n)~ có màu được mô tả bởi số nguyên ~a_i~.

Do sơ suất trong quá trình sản xuất, hộp màu có thể chứa một số cây cùng màu. Là người cầu toàn, Phát muốn bỏ bớt một số cây sao cho các cây còn lại có màu đôi một khác nhau.

Phát được bỏ đi nhiều nhất một đoạn gồm các cây màu liên tiếp: chọn hai số nguyên ~l~, ~r~ ~(1 \le l \le r \le n)~ rồi bỏ các cây từ vị trí ~l~ đến vị trí ~r~, giữ nguyên các cây còn lại (Phát cũng có thể không bỏ cây nào).

Hãy tìm số cây màu ít nhất phải bỏ đi để các cây còn lại thoả mãn điều kiện trên.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^6)~ là số cây màu.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le n)~.

Kết quả

In ra một số nguyên duy nhất là số cây màu ít nhất bị bỏ đi.

Subtask

• Subtask 1 (~20\%~ số điểm): ~n \le 10^2~.
• Subtask 2 (~20\%~ số điểm): ~n \le 10^3~.
• Subtask 3 (~30\%~ số điểm): ~n \le 10^5~.
• Subtask 4 (~30\%~ số điểm): không có ràng buộc gì thêm.

Sample Input 1

4
1 1 2 2

Sample Output 1

2

Giải thích

Phát có thể bỏ các cây từ vị trí ~2~ đến vị trí ~3~, còn lại hai cây có màu ~1~ và ~2~.

Sample Input 2

5
1 4 1 4 5

Sample Output 2

2

Giải thích

Có ba cách tối ưu: bỏ các cây từ vị trí ~1~ đến ~2~, từ ~2~ đến ~3~, hoặc từ ~3~ đến ~4~.

Nguồn: OLP Tin học MT&TN 2023 – Sơ loại – Bảng Không chuyên (đề trên LQDOJ).