407902: GYM102920 L Two Buildings

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

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

Write a program that, given a sequence of building heights, prints $$$\max_{1 \leq i < j \leq n} (h_i + h_j) \ast (j − i)$$$.

Your program is to read from standard input. The input starts with a line containing an integer $$$n$$$ ($$$2 \leq n \leq 1,000,000$$$), where $$$n$$$ is the number of buildings. The buildings are numbered $$$1$$$ to $$$n$$$ from left to right. The second line contains the heights of $$$n$$$ buildings separated by a space such that the $$$i$$$-th number is the height $$$h_i$$$ of the $$$i$$$-th building ($$$1 \leq h_i \leq 1,000,000$$$).

Your program is to write to standard output. Print exactly one line. The line should contain $$$\max_{1 \leq i < j \leq n} (h_i + h_j) \ast (j − i)$$$.

5
1 3 2 5 4

21

5
8 3 6 3 1

36