Description

小黄看着眼前的实验数据已经汗流浃背了，很显然，实验数据显示，这批样本并不能达到预期效果，这样下去论文就发不出去了，不要说别的，就连毕业都成问题！那么现在能做的事情只剩下一件了，那就是对实验数据进行一些优美的修改，只选取其中的部分数据，这样一来数据确实全部是实验产生的，又能达到预期效果。

现在有一个长度为 $n$ 的序列，表示这批样本的实验数据。为了让实验结果看起来足够稳定，请你找到一个长度大于等于 $2$ 的子段，使得该子段的方差最小，并告诉小黄这个最小的方差乘以子段长度平方的结果。

记序列的一个长度为 $m$ 的子段为 $a_1', a_2', \cdots, a_m'$，这个子段的平均数 $E(a') = \frac{a_1'+ a_2'+ \cdots+ a_m'}{m}$，这个子段的方差 $D(a') = E(a'^2) - E^2(a')$（其中 $E(a'^2) = \frac{a_1'^2+ a_2'^2+ \cdots+ a_m'^2}{m}$）。如果这个子段的方差是原序列所有子段中最小的，请输出 $D(a') \times m^2$。

本题有对应的 $easy$、$hard$ 版本，多个版本之间仅有数据范围的区别，通过困难版本的代码可以直接通过简单版本。本题为困难版本。

注：本题故事纯属虚构，小黄没有任何学术不端行为，也请同学们不要有学术不端行为。

Format

Input

第一行一个整数 $n\ (2 \leq n \leq 10^6)$，表示序列的长度。

第二行有 $n$ 个整数 $a_1, a_2, \cdots, a_n\ (0 \leq a_i \leq 1000)$，表示实验数据。

Output

一个整数，表示最小的方差乘以子段长度平方的结果 $D(a') \times m^2$。

Samples

3
1 2 1

2

Limitation

1s, 1024KiB for each test case.