题目背景

给一个数组，每次可以删除一段回文子串。最少删几次清空数组？

题目描述

$\texttt{Genos}$ 最近在他的手机上下载了祖玛游戏。在祖玛游戏里，存在 $n$ 个一行的宝石，第 $i$ 个宝石的颜色是 $C_i$。这个游戏的目标是尽快的消灭一行中所有的宝石。

在一秒钟，$\texttt{Genos}$ 能很快的挑选出这些有颜色的宝石中的一个回文的、连续的子串，并将这个子串移除。每当一个子串被删除后，剩余的宝石将连接在一起，形成一个新的行列。

你的任务是：求出把整个宝石串都移除的最短时间。

输入格式

第一行包含一个整数 $n(1 \le n \le 500)$，表示宝石串的长度。第二行包含 $n$ 个被空格分开的整数，第 $i(1 \le i \le n)$ 个表示这行中第 $i$ 个珠子的颜色。

输出格式

输出一个整数，把这行珠子移除的最短时间。

输入输出样例 #1

输入 #1

7
1 4 4 2 3 2 1

输出 #1

2

输入输出样例 #2

输入 #2

5
3 3 4 4 1

输出 #2

3

输入输出样例 #3

输入 #3

8
7 7 2 3 7 3 7 8

输出 #3

4

说明/提示

样例说明

在第一个例子中，为了达到 $2$ 秒的最快时间，先移除回文串 $\texttt{4 4}$,再移除回文串 $\texttt{1 2 3 2 1}$