题目描述

小明生成了一个长度为 $n$ 的正整数数组 $a_1, a_2, \dots , a_n$，他可以选择连续的一段数 $a_l, a_{l+1}, \dots, a_r$，如果其中所有数都相等即 $a_l = a_{l+1} = \dots = a_r$，那么他可以获得 $(r - l + 1) \times a_l$ 的分数。

在选择之前，为了让分数尽可能大，他决定先选择数组中的一段区间，对其进行左右翻转。他想知道在对数组进行翻转之后他能获得的最大分数是多少？

提示：当翻转 $a_l$ 到 $a_r$ 这段区间后，整个数组会变为：

$$a_1, a_2, \dots , a_{l-1}, a_r, a_{r-1}, \dots , a_{l+1}, a_l, a_{r+1}, \dots , a_n $$

输入格式

输入共两行。

第一行为一个正整数 $n$。

第二行为 $n$ 个由空格分开的正整数 $a_1, a_2, \dots , a_n$。

输出格式

输出共 $1$ 行，一个整数表示答案。

样例

7
4 4 3 3 2 1 3

9

解释 #1

翻转区间 $[5, 7]$，数组变为 $4, 4, 3, 3, 3, 1, 2$，最大分数为选择三个 $3$。

数据范围

• 对于 $20\%$ 的评测用例，$n \leq 500$。
• 对于 $100\%$ 的评测用例，$1\leq n \leq 10^6$，$1\leq a_i \leq 10^6$。