题目描述

在“极东魔术午睡结社之夏”的社团活动室里，$Rikka$宣称自己发现了一种能测量“不可视境界线”能量波动的新魔法阵。这个魔法阵由一排共$n$颗蕴含着不同魔力值$a[i]$的水晶石组成。 $Rikka$的理论是：当两颗水晶石产生共鸣时，其共鸣强度不仅取决于它们自身的魔力之和，还受到它们魔力差异的剧烈程度以及物理距离的影响。这种复杂的共鸣现象，被她命名为“邪王真眼の共鸣干涉”。 作为社团里最可靠（或者说最被迫靠谱）的成员，富樫勇太需要验证$Rikka$那听起来很酷但总是漏洞百出的理论。他需要你的帮助。

给定一个长度为$n$的数组$a$，其中$a[i]$代表第$i$颗水晶石的魔力值。 请你帮助勇太计算，在所有位置不同的水晶石对（即$i≠j$）中，其“共鸣干涉强度”的最大值。共鸣干涉强度的计算公式为：

$$强度 = {(a[i] + a[j]) * |a[i] - a[j]| \over |i - j|} $$

输入格式

第一行：一个整数$n(2≤n≤10^6)$，表示水晶石的数量。 第二行：$n$个整数，表示数组$a$中的每个元素$(1≤a[i]≤10^9)$。

输出格式

一个整数，表示所有不同水晶石对中，“共鸣干涉强度”的最大值。结果只保留整数部分。

样例

5
1 2 3 4 5

9