Description

n 个小球从左到右排成一排，每个小球上都标有一个数值。接下来进行若干次操作，每次从以下操作中任选一项：

1、移走一个小球，本次操作获得 1 积分；

2、移走 k（k≥2）个小球，要求 k 个小球上的数值相同且位置连续，本次操作获得 k×k 的积分。

注：每次小球被移走后，剩余小球相对顺序不变，从左到右重新排成一排。

给定n 个小球从左到右的数值，请计算将这 n 个小球全部移走后可获得的总积分的最大值。

例如：n = 5；5 个小球从左到右的数值依次为 1、1、4、1、5；可按以下操作移走小球：

第一次：将1、1、4、1、5 中数值为 4 的小球移走，剩余小球排列为 1、1、1、5，本次操作获得 1 积分；

第二次：将1、1、1、5 中数值为 1 的 3 个小球移走，剩余小球排列为 5，本次操作获得 9（3×3）积分；

第三次：将数值为5 的小球移走，本次操作获得 1 积分；

最终获得的总积分的最大值为11（1 + 9 + 1）。

Input Format

第一行输入一个整数n（1≤n≤100），表示小球的数量

第二行输入n 个整数（1≤整数≤100），表示从左到右每个小球的数值，整数之间以一个空格隔开

Output Format

输出一个整数，表示总积分的最大值

5
1 1 4 1 5

11

Source