小明在玩一个摧毁回文的游戏。在游戏中，存在 n 长度的字符串，其中第 i 个具有字符为 ci。游戏的目标是尽快摧毁字符串中的所有字符。

在一秒钟内，小明能够准确地选择一个连续的回文字符串，并将其从字符串中删除。移除子串后，剩余的宝石再次移动以形成一个新的字符串。销毁整个字符串所需的最小秒数是多少？

让我们提醒一下，字符串（或子字符串）称为回文，如果它向后或向前读取相同。

输入的第一行包含一个整数 n（1 ≤ n ≤ 600）——宝石的数量。

第二行包含 n 个空格分隔的整数，其中第i 个字符串是 c i （1 ≤ c i ≤ n） 

打印单个整数 — 销毁整行所需的最小秒数。

样例说明：

在第一个样本中，可以在一秒钟内摧毁整个字符串。

在第二个样本中，一次只能摧毁一个字符，因此摧毁需要三秒钟。

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

40% n<= 20

100% n<=600