Chloe recently installed Zuma on her phone. The player is given a row of n gems, the i-th of which has the color c
i. The purpose of the game — destroy all stones in as few seconds as possible.
In one second, Chloe can choose any substring (a sequence of adjacent stones) that is a palindrome and delete it. After removing this substring, the remaining stones are shifted to form a continuous row again. What is the minimum number of seconds needed to destroy the entire line?
Recall that a string (or substring) is a palindrome if it reads the same from left to right as from right to left. In this case, this means that the color of the first stone is equal to the color of the last stone, the color of the second is equal to the color of the penultimate one, and so on.
Input:
The first line of the input contains a single integer n (1 ≤ n ≤ 500) — the number of stones in the initial row.
The second line contains n integers, the i-th of which is equal to c
i (1 ≤ c
i ≤ n) — the color of the i-th stone in the initial row.
Output:
Print a single integer — the minimum number of seconds required to remove all gems.
Examples:
| Input |
Output |
3
1 2 1
| 1 |
3
1 2 3
| 3 |
7
1 4 4 2 3 2 1
| 2 |
Explanations:
The sequence in the third example is [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []