Sau khi chán nghệ thuật hai chiều thông thường và bực mình vì người khác sao chép tác phẩm, nghệ sĩ bò vĩ đại Picowso quyết định chuyển sang phong cách một chiều tối giản hơn. Bức tranh mới nhất của cô được mô tả bằng một mảng màu một chiều độ dài \(N\) (\(1\le N\le300\)), trong đó mỗi màu là một số nguyên thuộc đoạn \(1\ldots N\).

Moonet, đối thủ của Picowso, đã tìm ra cách sao chép cả những bức tranh một chiều này! Trong mỗi nét cọ, Moonet tô một đoạn liên tiếp bằng một màu duy nhất, chờ khô rồi tô một đoạn khác, và cứ thế tiếp tục. Moonet có thể dùng mỗi màu trong \(N\) màu bao nhiêu lần tùy ý, kể cả không lần nào.

Hãy tính số nét cọ ít nhất để Moonet sao chép bức tranh một chiều mới nhất của Picowso.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng tiếp theo chứa \(N\) số nguyên thuộc đoạn \(1\ldots N\), biểu thị màu của từng ô trong bức tranh một chiều.

Dữ liệu ra

In số nét cọ ít nhất cần để sao chép bức tranh.

Phân nhóm

• Trong các test 2-4, bức tranh chỉ có màu \(1\) và \(2\).
• Trong các test 5-10, màu của ô thứ \(i\) thuộc đoạn

với mọi \(1\le i\le N\).

• Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

10
1 2 3 4 1 4 3 2 1 6

6

0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 0
1 2 2 2 2 2 2 2 1 0
1 2 3 3 3 3 3 2 1 0
1 2 3 4 4 4 3 2 1 0
1 2 3 4 1 4 3 2 1 0
1 2 3 4 1 4 3 2 1 6

Nguồn

USACO 2021 February Contest, Gold - Modern Art 3: https://usaco.org/index.php?page=viewproblem2&cpid=1114

Tác giả: Brian Dean và Benjamin Qi.