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}~ và xóa 2 phần tử ~i~ và ~i + 1~ thay thế chúng bằng phần tử có giá trị ~a_i + 1~. Hỏi độ dài nhỏ nhất có thể của mảng ~a~ là bao nhiêu.

Input

• Dòng đầu tiên gồm số tự nhiên ~n \le 500~.
• Dòng tiếp theo gồm ~n~ số tự nhiên của mảng ~a~ và ~\le 1000~.

Output

• Độ dài nhỏ nhất có thể của mảng ~a~.

Sample Test

Input:

7
3 3 4 4 4 3 3

Output:

2