该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

给一个数组，每次可以把相邻且相等的两个数合并成一个 $a_i+1$ 。求最多操作多少次/最少剩几个数？

题目描述

给你一个数组 $a_1,a_2,\cdots ,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

输入 #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

说明/提示