题目内容

有一天，小A在玩一款消消乐游戏。这个游戏和一般的消消乐有所不同。

游戏中 n 个方块，按编号从 1 到 n 按顺序排成一列。每个方块有一个颜色，第 i 个方块的颜色为 $c_ i$。游戏的流程是，每次选择一个方块，这个方块和其相连的所有相同颜色的方块都会被消除，消除后两边的方块会向中间移动重新组合。

例如，当前的方块为 12222232，选择除了最后面的任意一个 2 消除，所有中间的 2 都会被消除掉，最终方块变为 132。

每次消除都会得到一定的分数。设这次消除共消除了 k 个方块，那么这次消除得到的分数为 $k^2$ 。上例中的消除得分为 $5^2$ =25 。

不断重复以上流程，直到所有的方块全部被消除后游戏结束，将每次消除的分数相加作为最终得分。

小A想知道，给定初始的所有 n 个方块及其顺序，能够得到的最大分数是多少。

例如，方块序列为 12121。可以按照从左到右的顺序消除，最终得分为 5。可以先消除中间的 1 得到 1221，再消掉中间的两个 2 得到 11 最后一并消除，最终得分 1+4+4=9。最优方案为先依次消掉两个 2 得到 111，最后一并消除。最终得分 1+1+9=11。

输入格式

第一行一个整数 n 。

第二行 n 个整数，表示从左到右的顺序每个方块的颜色 $c_i$。

输出格式

一行一个整数表示答案。

样例 1

输入

5  
1 2 1 2 1

输出

11