给你一个数组 $$$a_1, a_2, \dots, a_n$$$。您可以多次执行以下操作:
- 选择一对两个相邻的相等元素 $$$a_i = a_{i + 1}$$$ (如果至少有一个这样的对)。
- 将它们替换为值为 $$$a_i + 1$$$ 的一个元素。
每次这样的操作之后,数组的长度将减少一(并且元素会相应地重新枚举)。您可以获得的数组 $$$a$$$ 的最小可能长度是多少?
输入
第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 500$$$) — 数组 $$$a$$$ 的初始长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — 初始数组 $$$a$$$。
输出
打印唯一的整数——执行上述操作任意次数后可以获得的最小可能长度。
示例
输入 #1
5 4 3 2 2 3
输出 #1
2
输入 #2
7 3 3 4 4 4 3 3
输出 #2
2
输入 #3
3 1 3 5
输出 #3
3
输入#4
1 1000
输出#4
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$$$。
在第三次和第四次测试中,您根本无法执行该操作。