在水平街道上排列着 $n$ 座建筑物。这些建筑物沿街道彼此相邻，从左到右第 $i$ 座建筑物的宽度为 1，高度为 $h_i$。我们需要在 $n$ 座建筑物中找到两座建筑物，设为第 $i$ 座和第 $j$ 座（满足 $i < j$），使得 $(h_i + h_j) * (j - i)$ 的值最大。

例如，右图展示了 5 座建筑物，从左到右的高度分别为 1, 3, 2, 5, 4。如果我们选择前 2 座建筑物，则得到 $(1 + 3) * (2 - 1) = 4$。如果我们选择第 1 座和第 5 座建筑物，则得到 $(1 + 4) * (5 - 1) = 20$。最大值由第 2 座和第 5 座建筑物取得，它们的高度分别为 3 和 4：$(3 + 4) * (5 - 2) = 21$。

编写一个程序，给定建筑物高度序列，输出 $\max_{1 \le i < j \le n} (h_i + h_j) * (j - i)$。

输入格式

程序从标准输入读取数据。输入的第一行包含一个整数 $n$ ($2 \le n \le 1,000,000$)，表示建筑物的数量。建筑物从左到右编号为 1 到 $n$。第二行包含 $n$ 个用空格分隔的建筑物高度，其中第 $i$ 个数字是第 $i$ 座建筑物的高度 $h_i$ ($1 \le h_i \le 1,000,000$)。

输出格式

程序将结果写入标准输出。仅输出一行，包含 $\max_{1 \le i < j \le n} (h_i + h_j) * (j - i)$ 的值。

样例

样例输入 1

5
1 3 2 5 4

样例输出 1

21

样例输入 2

5
8 3 6 3 1

样例输出 2

36