Description

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.

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 a single 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 (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:

#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

Translated by ChatGPT 5