CF1312E.Array Shrinking

You are given an array $a_1, a_2, \dots, a_n$. You can perform the following operation any number of times:

• Choose a pair of two neighboring equal elements $a_i = a_{i + 1}$ (if there is at least one such pair).
• Replace them by one element with value $a_i + 1$.

After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array $a$ you can get?

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

• 选择一对相邻且相等的元素 $a_i = a_{i + 1}$（要求至少存在这样的一对）；
• 将它们替换为一个值为 $a_i + 1$ 的元素。

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

The first line contains the single integer $n$ ($1 \le n \le 500$) — the initial length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000$) — the initial array $a$.

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

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

Print the only integer — the minimum possible length you can get after performing the operation described above any number of times.

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

In the first test, this is one of the optimal sequences of operations: $4$ $3$ $2$ $2$ $3$ $\rightarrow$ $4$ $3$ $3$ $3$ $\rightarrow$ $4$ $4$ $3$ $\rightarrow$ $5$ $3$.

In the second test, this is one of the optimal sequences of operations: $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$.

In the third and fourth tests, you can't perform the operation at all.

在第一个测试用例中，以下是一种最优的操作序列：$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$。

在第三和第四个测试用例中，你根本无法执行该操作。