题目描述

Genos 最近在他的手机上下载了祖玛游戏。在祖玛游戏里，存在 $n$ 个排成一行的宝石，第 $i$ 个宝石的颜色是 $c_{i}$。这个游戏的目标是尽快地消除一行中所有的宝石。在一秒中，Genos 能很快地挑选出这些有颜色的宝石中的一个回文的、连续的子串，并将这个子串消除。每当一个子串被消除后，剩余的宝石将连接在一起，形成一个新的串。你的任务是：求出把整个宝石串都移除的最短时间。

如果一个串正着读或倒着读都一样，那么这个串（或子串）叫回文串。在我们这道题中，“回文”指这个子串中的第一个珠子的颜色等于最后一个珠子的颜色，第二个珠子的颜色等于倒数第二个珠子的颜色，等等。

输入格式

第 $1$ 行包含 $1$ 个整数 $n$，表示宝石串的长度。

第 $2$ 行包含 $n$ 个被空格分开的整数，第 $i$ 个数 $c_{i}$ 表示第 $i$ 个珠子的颜色。

输出格式

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

说明与提示

在第一个例子中，Genos 可以在一秒钟就把这行珠子全部移走。

在第二个例子中，Genos 一次只能移走一个珠子，所以移走三个珠子花费他三秒。

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

来源

浩轩OJ 4385 · 原题图片

数据范围与约定

$1\le n\le500$，$1\le c_{i}\le n$。

可见测试数据

输入数据 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