题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$。你可以对这个数列进行任意次如下操作：

选择数列中相邻的两个数值相同的元素 $a_i = a_{i+1}$，并用一个新的数值为 $a_i + 1$ 的元素替换掉这两个元素。

每进行一次操作，数列的长度就会减小 $1$（并且数列中的元素下标也会重新计算）。

求：你最终能够得到的最小的数列长度是多少？

输入格式

第一行，一个整数 $n(1 \le n \le 500)$，表示初始时数列的长度。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 1000)$，两两之间以一个空格分隔。

输出格式

输出一个整数，表示最终能够得到的最小的数列长度。

样例

5
4 3 2 2 3

2

7
3 3 4 4 4 3 3

2

3
1 3 5

3

1
1000

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}$

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

数据规模与约定

• 对于 $50\%$ 的数据，$n \le 50$
• 对于 $100\%$ 的数据，$1 \le n \le 500, 1 \le a_i \le 1000$