Chia nhóm (Grouping)

Nguồn: Kỳ thi chọn HSG thành phố Hà Nội và chọn đội tuyển HSG dự thi Olympic quốc gia các môn văn hóa lớp 12 THPT năm học 2026–2027 — Môn Tin học (Bảng A), Bài 5
Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy số gồm $N$ số nguyên $A_1,A_2,\ldots,A_N$. Cần chia dãy thành các nhóm sao cho:

• Mỗi nhóm chứa ít nhất một phần tử.
• Mỗi nhóm gồm các phần tử liên tiếp của dãy.
• Mỗi phần tử thuộc đúng một nhóm.
• Không có giá trị nào xuất hiện trong nhiều hơn $2$ nhóm.

Ví dụ, với $A=[1,2,1,1,1,2]$, có thể chia thành $4$ nhóm:

$[1]\mid[2]\mid[1,1,1]\mid[2]$.

Cách chia $[1]\mid[2]\mid[1,1]\mid[1,2]$ không hợp lệ vì giá trị $1$ xuất hiện trong $3$ nhóm.

Hãy tìm cách chia dãy thành nhiều nhóm nhất và in ra số nhóm lớn nhất có thể tạo được.

Input

• Dòng đầu tiên chứa số nguyên dương $N$.
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\ldots,A_N$.

Output

In ra một số nguyên dương là số lượng nhóm lớn nhất có thể chia được.

Subtask

• Ràng buộc chung: $1\le N\le 2\times10^5$, $|A_i|\le10^9$.
• Subtask 1 — $30$ điểm: $N\le20$.
• Subtask 2 — $30$ điểm: dãy đã cho theo thứ tự không giảm.
• Subtask 3 — $20$ điểm: $N\le2000$.
• Subtask 4 — $20$ điểm: không có ràng buộc thêm.

Ví dụ

Input

5
1 2 1 2 1

Output

3

Giải thích

Có thể chia thành $3$ nhóm, chẳng hạn:

$[1]\mid[2]\mid[1,2,1]$.

Khi đó giá trị $1$ xuất hiện trong nhóm thứ nhất và nhóm thứ ba; giá trị $2$ xuất hiện trong nhóm thứ hai và nhóm thứ ba. Mỗi giá trị đều xuất hiện trong không quá $2$ nhóm. Không thể chia dãy thành $4$ nhóm mà vẫn thỏa mãn yêu cầu.