「EZEC-5」人赢

> “我们在 小 Z 面前秀个恩爱吧。”\ >“好的。” 小 Z 发现他身边都是人赢，这使他非常自闭。 小 Z 又看着身边的潇，不禁陷入了沉思…… 

潇有一个数组 $k$，下标为 $1$ 到 $n$ 。 潇定义 $f(x,y)=\begin{cases} \min(k_x,k_y) \times (x + y) &x \ne y \\ k_x\times x&x=y \end{cases}$ 。 潇想知道对于任意的 $1 \le x,y \le n$，$f(x,y)$ 的最大值是多少。但是她不会做，于是就问了善良的 小 Z，然而非常想在妹子面前表现的 小 Z 发现他也不会做，就只能够求助善良的你了。

第一行一个整数 $n$。 第二行 $n$ 个整数 $k$，第 $i$ 个整数为 $k_i$。含义如上文。

一行一个整数，表示对于任意的 $1 \le x,y \le n$，$f(x,y)$ 的最大值。

3
3 2 1

6

5
3 4 5 4 3

28

### 数据范围 **本题采用捆绑测试。** - Subtask 1（20 points）：$1 \le n \le 5000$。 - Subtask 2（10 points）：保证所有 $k_{i}$ 都相等。 - Subtask 3（20 points）：$k_i \le 10^3$。 - Subtask 4（50 points）：无特殊性质。 对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le k_{i} \le 10^9$。 ------------ 本题加强版：[link](https://www.luogu.com.cn/problem/P7291)。