DEL

Points: 100

Time limit: 1.0s

Memory limit: 495M

Problem type

Minh và Hồng cùng chơi trò chơi xóa số như sau:

Minh viết một dãy gồm \(n\) số \(a_1, a_2, …, a_n\), sau đó Hồng sẽ tìm cách xóa số theo quy tắc: Mỗi bước Hồng được chọn một dãy liên tiếp các số giống nhau rồi xóa bỏ các số đó. Sau khi xóa xong, các số được dồn lại và Hồng lại tiếp tục xóa cho đến khi xóa hết tất cả các số. Một cách xóa được gọi là thông minh nếu số bước xóa phải thực hiện là ít nhất.

Sau khi xóa xong dãy số, để chứng minh cách xóa của mình là thông minh, hơn nữa Hồng muốn chứng minh kỹ thuật lập trình của mình, Hồng đã quyết định viết một chương trình tính số bước xóa ít nhất cần thực hiện với một dãy số bất kì.

Yêu cầu: Cho dãy gồm \(n\) số \(a_1, a_2, …, a_n\), hãy tính số bước xóa ít nhất cần thực hiện