3686. 回文串

单点时限: 2.0 sec

内存限制: 512 MB

QQ 小方以前不会判断回文数列,现在他会了,所以他急切的想教会你。

回文数列指的是一个正读和反读都一样的数列,比如 “1 2 3 2 1” 和 “1 2 2 1”。

单单讲给你听肯定是不够的,为了表现自己,QQ 小方现在要考考你。

现在 QQ 小方会给你 个数组成的数列 。他每次操作允许你合并其中相邻的两个数 (),合并以后的两个数留在原来的位置(两个数合并以后只会留下一个数),但会变成 。QQ 小方想知道最少需要几次这样的操作,这个数列就会变成回文数列。

输入格式

输入包含两行,第一行一个整数 (),表示数列的长度。

第二行包含 个用空格隔开的数 (),表示数列。

输出格式

输出包含一个整数,表示最少的操作次数。

样例

Input
3
1 2 3
Output
1
Input
3
1 2 4
Output
2
Input
3
3 3 3
Output
0

提示

对于样例一:只需要一步,即合并前两个。

对于样例二:只有合并成一个数的时候,才满足回文数列的要求,所以需要两步。

对于样例三:本身就是一个回文数列,不需要合并操作。

808 人解决,955 人已尝试。

870 份提交通过,共有 3432 份提交。

1.5 EMB 奖励。

创建: 6 月,4 周前.

修改: 6 月,3 周前.

最后提交: 2 周,1 天前.

来源: N/A

题目标签