题目描述

有一列 $n$ 颗宝石，第 $i$ 颗宝石的颜色为 $c_i$。

每一秒你可以选择当前宝石序列中的一个非空连续回文子段并将其删除。删除后，左右两侧剩余的宝石会拼接成一列新的连续序列。

若一个宝石序列从左到右和从右到左的颜色顺序完全相同，则称它是回文的。求删除全部宝石所需的最少秒数。

输入格式

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

第二行输入 $n$ 个整数 $c_1,c_2,\dots,c_n$（$1 \le c_i \le n$），表示各宝石的颜色。

输出格式

输出一个整数，表示删除全部宝石所需的最少秒数。

样例

样例 1

输入：

3
1 2 1

输出：

1

样例 2

输入：

3
1 2 3

输出：

3

样例 3

输入：

7
1 4 4 2 3 2 1

输出：

2