题目描述

相信王老师很喜欢玩淘汰游戏，对此就不再赘述。淘汰游戏大致规则是：给班上排成一排的学生每人一个淘汰值，每次可以消去任意一段连续的回文淘汰值（单个淘汰值也是回文），问最少消几次能消完。

输入描述

第一行 1 个整数 n，表示学生人数；
第二行 n 个整数 a1, a2, ..., an 表示淘汰值。

输出描述

输出最少次数。

样例1

输入

3
1 2 1

输出

1

样例2

输入

3
1 2 3

输出

3

样例3

输入

7
1 4 4 2 3 2 1

输出

2

数据范围

对于 30%的数据，1 <= n <= 100；
对于 100%的数据，1 <= n <= 500, 1 <= ai <= n。

限制

1s

样例解释

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

来源

Codeforces607B
CWOI新高二专题测试七