CF607B.Zuma

Genos recently installed the game Zuma on his phone. In Zuma there exists a line of n gemstones, the i-th of which has color c__i. The goal of the game is to destroy all the gemstones in the line as quickly as possible.

In one second, Genos is able to choose exactly one continuous substring of colored gemstones that is a palindrome and remove it from the line. After the substring is removed, the remaining gemstones shift to form a solid line again. What is the minimum number of seconds needed to destroy the entire line?

Let us remind, that the string (or substring) is called palindrome, if it reads same backwards or forward. In our case this means the color of the first gemstone is equal to the color of the last one, the color of the second gemstone is equal to the color of the next to last and so on.

Genos 最近在手机上安装了游戏 Zuma。在 Zuma 中，有一排共 $n$ 颗宝石，其中第 $i$ 颗宝石的颜色为 $c_i$。游戏的目标是以尽可能快的速度清空整排宝石。

每秒钟，Genos 可以恰好选择一个连续的、颜色序列构成回文的子串，并将其从该排中移除。移除后，剩余的宝石会向中间靠拢，重新形成一排连续的宝石。问：清空整排宝石所需的最少秒数是多少？

我们回顾一下：若一个字符串（或子串）正读与反读完全相同，则称其为回文串。在本题中，这意味着该子串首尾宝石颜色相同，第二颗与倒数第二颗颜色相同，依此类推。

The first line of input contains a single integer n (1 ≤ n ≤ 500) — the number of gemstones.

The second line contains n space-separated integers, the i-th of which is c__i (1 ≤ c__i ≤ n) — the color of the i-th gemstone in a line.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 500$）—— 表示宝石的数量。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个整数为 $c_i$（$1 \leq c_i \leq n$）—— 表示第 $i$ 颗宝石的颜色。

Print a single integer — the minimum number of seconds needed to destroy the entire line.

输出一个整数——摧毁整条线所需的最少秒数。

In the first sample, Genos can destroy the entire line in one second.

In the second sample, Genos can only destroy one gemstone at a time, so destroying three gemstones takes three seconds.

In the third sample, to achieve the optimal time of two seconds, destroy palindrome 4 4 first and then destroy palindrome 1 2 3 2 1.

在第一个样例中，Genos 可以在一秒内摧毁整行宝石。

在第二个样例中，Genos 每次只能摧毁一颗宝石，因此摧毁三颗宝石需要三秒。

在第三个样例中，为达到最优时间两秒，应先摧毁回文子序列 $4\ 4$，再摧毁回文子序列 $1\ 2\ 3\ 2\ 1$。