1400: 盖大楼

Sakits 要建楼啦！

现在东川路上有 $n$ 个地块排成一排，每个地块有一个购买的价格 $a_i$。Sakits 打算在路上挑出 $i$ 和 $j$ 两个地块盖楼。

为了彰显他的财大气粗，Sakits 打算尽量挑贵的地块盖楼——就是说，他想让 $a_i + a_j$ 尽量大。

另外，他还不想让两栋楼离得太近。换句话说，他还想要 $|i - j|$ 尽量大。

为了满足 Sakits 的两个愿望，地产公司想出了一个绝妙的主意：找到两个地块，使得这两个地块的“价值” $(a_i+a_j) \cdot |i - j|$ 是这条路上最大的，不就可以了吗？

可惜地产公司的电脑太差了，算不出最大的价值是多少...... 你能帮帮 Sakits 吗？

第一行一个整数 $n$，表示地块的数量

接下来一行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示 $i$ 号地块的价格

一行一个整数，表示挑出的两个最大地块的价值。

text 5 8 3 6 3 1

text 36

对于 $10 \%$ 的数据，$1 ≤ n ≤ 1000$；
对于 $50 \%$ 的数据，$1 ≤ n ≤ 100000$，保证数据随机生成；
对于 $100 \%$ 的数据，$1 ≤ n ≤ 1000000$，$1 ≤ a_i ≤ 1000000$。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！