题目描述

最近，汪老师在手机上安装了游戏《回文消消乐》。在《回文消消乐》中存在一行共 $n$ 颗宝石，其中第 $i$ 颗宝石的颜色为 $c_i$。游戏的目标是尽快摧毁整行宝石。

在一秒钟内，汪老师能够选择一个连续的回文颜色宝石子串并将其从行中移除。在子串被移除后，剩余的宝石会重新排列成一行。

求：摧毁整行所需的最少秒数是多少？

说明：字符串（或子串）被称为回文，如果它从前往后读和从后往前读是一样的。在本题的情景下，这意味着第一个宝石的颜色等于最后一个宝石的颜色，第二个宝石的颜色等于倒数第二个宝石的颜色，……，依此类推。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 500$），表示宝石的数量。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个整数为 $c_i$（$1 \le c_i \le n$），表示 第 $i$ 颗宝石的颜色。

输出格式

输出一个整数，表示摧毁整行所需的最少秒数。

样例

3
1 2 1

1

3
1 2 3

3

7
1 4 4 2 3 2 1

2

说明/提示

样例解释

在第一个示例中，汪老师可以在一秒钟内摧毁整行。

在第二个示例中，汪老师每次只能摧毁一个宝石，因此摧毁三个宝石需要三秒。

在第三个示例中，为了达到最优的两秒时间，首先摧毁回文4 4，然后摧毁回文1 2 3 2 1。