题目描述

小可最近在他的手机上安装了一个新游戏。在这个游戏中，存在一行 $n$ 个宝石，其中第 $i$ 个宝石的颜色为 $c_i$。游戏的目标是尽快地摧毁这一行中的所有宝石。

在每一秒内，小可可以选择一个恰好是回文的连续子串颜色的宝石，并将其从这一行中移除。移除子串后，剩余的宝石会重新排列成一行。请问，摧毁整行宝石所需的最少秒数是多少？

提醒一下，如果一个字符串（或子串）正读和反读都一样，那么它被称为回文。这意味着第一个宝石的颜色等于最后一个宝石的颜色，第二个宝石的颜色等于倒数第二个宝石的颜色，以此类推。

输入格式

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

输入的第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个整数是 $c_i$（$1 \leq c_i \leq n$）——这一行中第 $i$ 个宝石的颜色。

输出格式

输出一个整数——摧毁整行宝石所需的最少秒数。

样例

3
1 2 1

1

3
1 2 3

3

7
1 4 4 2 3 2 1

2

提示

在第一个示例中，小可可以在一秒内摧毁整行宝石。$\\$ 在第二个示例中，小可每次只能摧毁一个宝石，所以摧毁三个宝石需要三秒。$\\$ 在第三个示例中，为了达到最优时间两秒，小可首先摧毁回文$4 4$，然后摧毁回文$1 2 3 2 1$。

数据范围

见输入格式。