#8314. 「JXOI Test Round 1」一道送分好题 省选/NOI−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: jxy2012

题目描述

正值盛夏之时,汐美学院的学生会长,图书部的部长 VVXR(雾)放开了所有的工作,和你,汐美学院 的天才学生兼年级第一,过着轻♂松而愉♀快的生活。

吃完饭,你便一头倒在了床上,而 VVXR 玩着你的壕级神机——Windows Phone 上的方块消除游戏。

憧憬着未来回老家结婚的你看着死党 VVXR 玩着你的手♂机,作为一个天才学生,你不合时宜地 想到了一个 OI 题。

“给定一个长度为 的方块序列,每次可以选择一段颜色相同的连续方块消除,若消除的这一段连续方块个数为 ,则得分为 ,如何消除所有的方块以得到尽量多的分数。”

然后注孤生的你就开始想这道该死的 OI 题了。如果你做不出来,今晚你可是无法触发与 VVXR 的日♀常的哦。

输入格式

包含两行,第一行仅有一个正整数 ,代表方块序列的长度。

第二行有一个长度为 的整数序列,其中每个整数代表一种颜色。

输出格式

仅包含一行,且仅有一个整数 ans,代表你能获得的最大分数。

样例

样例输入

9
1 2 2 2 2 3 3 3 1

样例输出

29

数据范围与提示

对于 数据,

对于 数据,

对于 数据,

对于 数据,颜色编号 保证 为正整数。