두 건물

길을 따라 $n$개의 건물이 일렬로 서 있다. 건물은 서로 이웃해 있고, 왼쪽에서 $i$번째 건물의 폭은 1, 높이는 $h_i$이다. $n$개의 건물 중에서 $i < j$인 두 건물, 즉 $i$번째 건물과 $j$번째 건물을 골라 $(h_i + h_j) \times (j - i)$가 최대가 되도록 한다.

예를 들어 왼쪽부터 높이가 1, 3, 2, 5, 4인 건물 5개를 생각해 보자. 왼쪽에서 두 건물을 고르면 $(1 + 3) \times (2 - 1) = 4$이다. 첫 번째 건물과 다섯 번째 건물을 고르면 $(1 + 4) \times (5 - 1) = 20$이다. 최댓값은 높이가 3인 두 번째 건물과 높이가 4인 다섯 번째 건물에서 나오며, $(3 + 4) \times (5 - 2) = 21$이다.

건물 높이의 열이 주어졌을 때 $\max_{1 \le i < j \le n} (h_i + h_j) \times (j - i)$를 출력하는 프로그램을 작성하라.

첫 줄에 건물의 수 $n$ ($2 \le n \le 1000000$)이 주어진다. 둘째 줄에는 왼쪽부터 $n$개 건물의 높이가 공백으로 구분되어 주어진다. $i$번째 수가 $i$번째 건물의 높이 $h_i$이다 ($1 \le h_i \le 1000000$).

$\max_{1 \le i < j \le n} (h_i + h_j) \times (j - i)$의 값을 한 줄에 출력한다.