Maximum Function Value

You are given an array \(k\) of length \(n\) (indexed from \(1\) to \(n\)). Define the function \(f(x,y)\) as follows:

\(f(x,y)=\begin{cases} \min(k_x,k_y)\times (x+y) & \text{if } x \ne y\\ k_x\times x & \text{if } x=y \end{cases}\)

Your task is to compute the maximum value of \(f(x,y)\) for any \(1 \le x,y \le n\).

inputFormat

The first line contains an integer \(n\) — the number of elements in the array. The second line contains \(n\) space-separated integers \(k_1, k_2, \ldots, k_n\) representing the array.

outputFormat

Output a single integer — the maximum value of \(f(x,y)\) among all pairs \(1 \le x,y \le n\).

sample

1
5

5