杰诺斯最近在他的手机上安装了祖玛游戏。在 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。