(ĐTQG Hà Nội 2024) Bài 3: Gộp dãy số

Cho dãy số gồm \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\).

Thao tác gộp dãy số được thực hiện như sau: chọn hai phần tử liên tiếp \(a_i\) và \(a_{i+1}\) có cùng giá trị \(x\), rồi xoá \(a_{i+1}\) khỏi dãy và tăng \(a_i\) lên thành \(x + 1\), sau đó các phần tử còn lại của dãy được dồn lại.

Yêu cầu. Hãy tìm cách thực hiện liên tục các thao tác trên để được dãy có ít phần tử nhất.

\InputFile

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \le N \le 10^6)\).
• Dòng thứ hai chứa \(N\) số nguyên \(a_i\) \((1 \le a_i \le 10^9;\ 1 \le i \le N)\).

\OutputFile

• Ghi ra số lượng phần tử ít nhất có thể của dãy sau khi thực hiện các thao tác gộp dãy số.

\Examples
\beginexample
\exmp
4
3 2 2 2

2

\endexample

\Note
Các bước gộp dãy số:

• Dãy ban đầu: \(3\;2\;2\;2\).
• Gộp hai số ở vị trí \(2\) và \(3\), dãy trở thành: \(3\;3\;2\).
• Gộp hai số ở vị trí \(1\) và \(2\), dãy trở thành: \(4\;2\).

\Scoring

• (\(20\%\)) \(N \le 10;\ a_i \le 30\);
• (\(20\%\)) \(N \le 200;\ a_i \le 30\);
• (\(20\%\)) \(N \le 2000;\ a_i \le 30\);
• (\(10\%\)) \(N \le 2000\);
• (\(10\%\)) \(a_i \le 30\);
• (\(20\%\)) Không có ràng buộc thêm.

\endproblem