题目描述

给定一个数组 $a_1, a_2, \ldots, a_n$。你可以任意多次执行以下操作：

• 选择一对相邻的相等元素 $a_i = a_{i + 1}$（如果存在至少一对）。
• 用值为 $a_i + 1$ 的一个元素替换它们。

每次执行这样的操作后，数组的长度将减少一个（元素相应地重新编号）。你能得到的数组 $a$ 的最小可能长度是多少？

输入格式

第一行包含一个整数 $n$（$1 \le n \le 500$）——数组 $a$ 的初始长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 1000$）——初始数组 $a$。

输出格式

输出一个整数——执行上述操作任意次后可能得到的最小长度。

样例

5
4 3 2 2 3

2

7
3 3 4 4 4 3 3

2

3
1 3 5

3

1
1000

1

说明/提示

样例解释

在第一个测试中，一种最优的操作序列是：$4\ 3\ 2\ 2\ 3 \rightarrow 4\ 3\ 3\ 3 \rightarrow 4\ 4\ 3 \rightarrow 5\ 3$

在第二个测试中，一种最优的操作序列是：$3\ 3\ 4\ 4\ 4\ 3\ 3 \rightarrow 4\ 4\ 4\ 4\ 3\ 3 \rightarrow 4\ 4\ 4\ 4\ 4 \rightarrow 5\ 4\ 4\ 4 \rightarrow 5\ 5\ 4\ \rightarrow 6\ 4$

在第三个和第四个测试中，你无法执行这个操作。