说明

相信大家都玩过祖玛游戏，对此就不在赘述。祖玛游戏大致规则是： 给一串数字，每次可以消去任意一段连续的回文数字（单个数字也是回文），问最少需要几次才能能消完。

输入格式

第一行 1 个整数$n$，表示数字长度

第二行$n$ 个整数表示 $a_{1},a_{2},a_{3}..a_{n}$

输出格式

输出只有一行，输出最少次数

样例

3
1 2 1

1

3
1 2 3

3

7
1 4 4 2 3 2 1

2

样例解释

样例 3：先消除 4 4，得到序列 1 2 3 2 1，是回文，全部消除，共 2 次。

数据范围

对于 30%的数据， $1 \leqslant n \leqslant 100$

对于 100%的数据， $1 \leqslant n \leqslant 500, 1 \leqslant a_{i} \leqslant n$

来源：Codeforces 607B