Nén mảng

Cho mảng \(a\) có \(n\) phần tử. Có thể thực hiện thao tác sau vô số lần: chọn chỉ số \(1 \le i \le n - 1\) sao cho \(a_i = a_{i + 1}\), xóa hai phần tử \(a_i\), \(a_{i + 1}\) và thay thế chúng bằng một phần tử duy nhất có giá trị \(a_i + 1\) (đặt vào đúng vị trí mà hai phần tử cũ chiếm trong mảng).

Hãy tìm độ dài nhỏ nhất có thể của mảng \(a\) sau khi thực hiện một số (có thể là \(0\)) thao tác như trên.

Input

• Dòng đầu tiên gồm một số tự nhiên \(n\) (\(1 \le n \le 500\)).

• Dòng thứ hai gồm \(n\) số tự nhiên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 1000\)).

Output

In ra một số nguyên duy nhất là độ dài nhỏ nhất có thể của mảng \(a\).

Example

Input:

7
3 3 4 4 4 3 3

Output:

2

Note

Với mảng \([3, 3, 4, 4, 4, 3, 3]\), ta có thể gộp hai phần tử \(3, 3\) ở đầu thành \(4\), được mảng \([4, 4, 4, 4, 3, 3]\). Gộp tiếp hai cặp \(4, 4\) liên tiếp thành \(5, 5\), được mảng \([5, 5, 3, 3]\). Gộp \(5, 5\) thành \(6\) và \(3, 3\) thành \(4\), được mảng \([6, 4]\), không thể gộp tiếp vì \(6 \ne 4\). Mảng cuối cùng có độ dài \(2\), đây là độ dài nhỏ nhất có thể đạt được.