牛娃喜欢对数组进行各种操作。今天，牛娃首先构建了一个数组a₁ a₂…a_n，然后牛娃可以对数组进行以下操作任意次数: 

    选择一对相邻的相等元素a_i=a_i+1(如果存在)，然后用一个值为a_i+1的元素代替它们。

    显然，在进行这样的操作之后，数组的长度将减少1(元素将相应地重命名)。 现在请你帮牛娃看看，牛娃能得到的数组的最小长度是多少?  

第一行包含一个整数n(1≤n≤500)，为数组a的初始长度。  

第二行包含n个整数a₁,a₂，…，a_n(1≤a_i≤1000)，为初始数组a。

一个整数，为对数组a执行上述操作任意次数后可以得到的最小数组长度。

5  
4 3 2 2 3

2

样例3：

输入

3

1 3 5 

输出

3

样例4：

输入

1 

1000 

输出

1 

请注意 ：

    在第一个测试中，一个最优的操作序列为:4 3 2 2 3→4 3 3 3→4 4 3→5 3。最后得到的数组长度为2。 

    在第二个测试中，一个最优的操作序列为:3 3 4 4 4 3 3→4 4 4 4 3 3→4 4 4 4 4→5 4 4 4→5 5 4→6 4。最后得到的数组长度为2。 

    在样例3和样例4中，您根本无法执行上述操作，数组不会改变。最后的数组长度和原始数组长度相同。