You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

抚仙湖的彩色石子

题目背景

抚仙湖以其清澈见底的湖水和色彩斑斓的石子闻名。假期里，小明在抚仙湖的沙滩上玩一个类似“祖玛”的消除游戏。

题目描述

沙滩上有一排共 $n$ 个彩色石子，每个石子都有一个颜色编号 $c_i$。 小明每次操作可以选中一段**连续且颜色对称（即回文）**的石子，并将它们全部消除。消除后，这段石子左右两边的石子会自然合拢，拼接在一起。 例如，对于石子序列 [1, 4, 4, 2, 3, 2, 1]：

• 小明可以先选择中间的回文段 [4, 4] 进行消除，剩下的石子合拢变成 [1, 2, 3, 2, 1]。
• 接着，剩下的序列本身就是一个回文串，小明可以再一次性将它们全部消除。总共只需 2 次操作。

小明想知道，要把沙滩上这排石子全部消除完，最少需要进行多少次操作？

输入格式

第一行包含一个正整数 $n$，表示彩色石子的总数。 第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$，依次表示每个石子的颜色编号。相邻整数之间用空格隔开。

输出格式

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

样例 #1

样例输入 #1

7
1 4 4 2 3 2 1

样例输出 #1

2

样例 #2

样例输入 #2

5
1 2 3 4 5

样例输出 #2

5

提示与数据范围

【样例解释 1】 先消除 4 4，变为 1 2 3 2 1；再消除 1 2 3 2 1，全部清空。共 2 次。

【样例解释 2】 没有任何长度大于 1 的回文子串，只能一个一个消除，共 5 次。

【数据范围】 对于 $30\%$ 的数据，满足 $1 \le n \le 20$。 对于 $100\%$ 的数据，满足 $1 \le n \le 500$，$1 \le c_i \le 1000$。