宝石消除

题目描述

Y 同学最近沉迷于一款名为“宝石消除”的手机游戏。游戏界面上初始排列着一行共 $N$ 个宝石，这些宝石的颜色由一个整数序列 $C = \{c_1, c_2, \ldots, c_N\}$ 表示，其中 $c_i$ 代表第 $i$ 个宝石的颜色。

游戏的核心机制是“回文消除”。在每一秒钟，Y 同学可以执行一次操作：选择当前宝石序列中的一个连续子串，如果该子串是回文串（即从左向右读和从右向左读完全相同），则可以将该子串整体移除。

当一个子串被移除后，其左右两边剩余的宝石（如果存在）会自动合并，连接在一起形成新的序列。

Y 同学的目标是用最少的时间（即最少的操作次数）将这一行宝石全部消除。请你帮助 Y 同学计算出达成目标所需的最少操作次数。

输入格式

第一行包含一个整数 $N$，表示初始宝石序列的长度。 第二行包含 $N$ 个用空格分隔的整数 $c_1, c_2, \ldots, c_N$，表示每个宝石的颜色。

输出格式

输出一行一个整数，表示将所有宝石消除所需的最少操作次数。

样例

样例输入 #1

3
1 2 1

样例输出 #1

1

样例输入 #2

3
1 2 3

样例输出 #2

3

样例输入 #3

7
1 4 4 2 3 2 1

样例输出 #3

2

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 500$，$1 \le c_i \le N$。