Two Buildings

There are $n$ buildings along a horizontal street. The buildings stand next to each other, and the $i$-th building from left to right has width 1 and height $h_i$. Among the $n$ buildings, choose two buildings, the $i$-th and the $j$-th with $i < j$, so that $(h_i + h_j) \times (j - i)$ is maximized.

For example, the figure shows 5 buildings with heights 1, 3, 2, 5, 4 from left to right. If we choose the first 2 buildings, we get $(1 + 3) \times (2 - 1) = 4$. If we choose the first and fifth buildings, we get $(1 + 4) \times (5 - 1) = 20$. The maximum is achieved by the second and fifth buildings, with heights 3 and 4: $(3 + 4) \times (5 - 2) = 21$.

Write a program that prints $\max_{1 \le i < j \le n} (h_i + h_j) \times (j - i)$.

The first line contains an integer $n$ ($2 \le n \le 1000000$), the number of buildings. The second line contains the heights of the $n$ buildings separated by spaces, from left to right, so that the $i$-th number is the height $h_i$ of the $i$-th building ($1 \le h_i \le 1000000$).

Print exactly one line containing $\max_{1 \le i < j \le n} (h_i + h_j) \times (j - i)$.