P7286 "EZEC-5" People Always Win.

> "Let's show off our affection in front of Xiao Z."\ > "Okay." Xiao Z found that everyone around him is always winning in life, 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$ 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.

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 one 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 (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](https://www.luogu.com.cn/problem/P7291)。 Translated by ChatGPT 5