P7291 "EZEC-5" Winner (Enhanced Version).

> "Let's show some affection in front of Xiao Z."\ > "OK." Xiao Z found that everyone around him is a “winner,” which made him very depressed. Xiao Z then looked at Xiao beside him and could not help falling into deep thought... 

Xiao has an array $k$ with indices 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 wants to show off in front of the girl, found that he also cannot solve it, so he has to ask the kind you for help.

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 one integer in a single line, representing the maximum value of $f(x,y)$ over all $1 \le x,y \le n$.

### Constraints **This problem uses bundled testdata.** - Subtask 1 (10 points): $1 \le n \le 50$. - Subtask 2 (20 points): $1 \le n \le 5000$. - Subtask 3 (20 points): $1 \le n \le 10^6$. - Subtask 4 (10 points): it is guaranteed that all $k_{i}$ are equal. - Subtask 5 (40 points): no special constraints. For $100\%$ of the testdata, $1 \le n \le 10^7$, $1 \le k_{i} \le 10^9$. **A faster input method is recommended for this problem.** Fast input used by std: ```cpp #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1