题面翻译

题目描述

给你一个长度为 $n(1 \le n \le 500)$ 的数组 $a$，每次你可以进行以下两步操作：

1. 找到 $i \in [1, n)$，使得 $a_i = a_{i + 1}$；

2. 将 它们 替换为 $a_i + 1$。

每轮操作之后，显然数组的长度会减小 $1$，问剩余数组长度的最小值。

输入格式

第一行包含一个整数 $n(1 \le n \le 500)$，表示数组的原长。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots a_n (1 \le a_i \le 1000)$，表示原数组 $a$。

输出格式

共一行仅一个整数 $num$，表示进行许多轮操作之后，$a$ 剩余长度的最小值。

样例 #1

样例输入 #1

5
4 3 2 2 3

样例输出 #1

2

样例 #2

样例输入 #2

7
3 3 4 4 4 3 3

样例输出 #2

2

样例 #3

样例输入 #3

3
1 3 5

样例输出 #3

3

样例 #4

样例输入 #4

1
1000

样例输出 #4

1

样例解释

第一组样例中，最优操作之一为 $\text{4 3 2 2 3} \to \text{4 3 3 3} \to \text{4 4 3} \to \text{5 3}$

第二组样例中，最优操作之一为 $\text{3 3 4 4 4 3 3} \to \text{4 4 4 4 3 3} \to \text{4 4 4 4 4} \to \text{5 4 4 4} \to \text{5 5 4} \to \text{6 4}$

对于第三和第四组样例，你并不能进行任何操作。

提示

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.