Description

Xiao has an array $k$ indexed from $1$ to $n$.

Xiao defines $f(x,y)=\begin{cases} \min(k_x,k_y) \times (x + y) &x \ne y \\ k_x\times x&x=y \end{cases}$.

Xiao wants to know, for any $1 \le x,y \le n$, what the maximum value of $f(x,y)$ is. But she cannot solve it, so she asked the kind Xiao Z. However, Xiao Z, who really wanted to impress the girl, found that he could not solve it either, so he can only ask for help from kind you.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $k$, where the $i$-th integer is $k_i$. The meaning is as described above.

Output Format

Output one integer in one line, representing the maximum value of $f(x,y)$ over all $1 \le x,y \le n$.

3
3 2 1

6

5
3 4 5 4 3

28

Hint

Constraints

This problem uses bundled testdata.

• Subtask 1 (20 points): $1 \le n \le 5000$.

• Subtask 2 (10 points): It is guaranteed that all $k_{i}$ are equal.

• Subtask 3 (20 points): $k_i \le 10^3$.

• Subtask 4 (50 points): No special properties.

For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le k_{i} \le 10^9$.

Enhanced version of this problem: link。

Translated by ChatGPT 5