← 返回题目列表

Codeforces · 607/B

B. 祖玛

中文机器翻译题面 查看原题

杰诺斯最近在他的手机上安装了祖玛游戏。在 Zuma 中,存在一行 n 颗宝石,其中第 i 颗宝石的颜色为 ci。游戏的目标是尽快摧毁队伍中的所有宝石。

在一秒钟内,杰诺斯能够准确地选择一个连续的回文有色宝石子串,并将其从行中删除。移除子串后,剩余的宝石再次移动形成实线。摧毁整条线路最少需要多少秒?

让我们提醒一下,如果向后或向前读取相同的字符串(或子字符串),则称为回文。在我们的例子中,这意味着第一颗宝石的颜色等于最后一颗宝石的颜色,第二颗宝石的颜色等于倒数第二颗宝石的颜色,依此类推。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 500) — 宝石数量。

第二行包含 n 个空格分隔的整数,其中第 i 个是 ci (1 ≤ ci ≤ n) – 一行中第 i 个宝石的颜色。

输出

打印单个整数 - 销毁整行所需的最少秒数。

示例

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

注意

在第一个样本中,杰诺斯可以在一秒内摧毁整条线路。

在第二个样本中,杰诺斯一次只能摧毁一颗宝石,因此摧毁三颗宝石需要三秒。

在第三个样本中,为了达到两秒的最佳时间,首先销毁回文 4 4,然后销毁回文 1 2 3 2 1。