Problem1487--PIPI的消消乐Ⅶ

1487: PIPI的消消乐Ⅶ

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 86  Solved: 36
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI最近又沉迷上了新的消消乐游戏。
给定一个含有n个正整数的序列,每次PIPI可以把一段连续的数字从序列中删除,要求这段连续的数字是回文的,删除后剩下的数字按原来的顺序拼接起来。比如:对于序列1 2 2 2 1,PIPI删除其中的2 2 2这段,剩下的元素按原来的顺序拼接起来,那么序列就变成了1 1。
请问PIPI最少要进行多少次操作,才能把所有数字都删除?

Input

输入一个正整数n,n<=300。
接下来n个正整数ai,ai<=10^9。

Output

输出PIPI最少要进行的操作次数。

Sample Input

5
1 2 2 2 1

Sample Output

1

Source/Category