数组翻转

题号：NC309238
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小明生成了一个长度为 $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$

输入描述:

输入共两行。

- 第一行为一个正整数 。
- 第二行为  个由空格分开的正整数 。

输出描述:

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

示例1

输入

复制

7
4 4 3 3 2 1 3

输出

复制

说明

翻转区间 ，数组变为 。
最大分数为选择三个 ，即 。

备注:

- 对于 20% 的评测用例，。
- 对于 100% 的评测用例，。