Long has an array $$$a$$$ consisting of $$$n$$$ elements $$$a_1,a_2,...,a_n$$$. Help Long find the maximum value of $$$P=\left(\sum_{k=i}^j a_k\right)^2-\sum_{k=i}^j a_k^2$$$ with $$$1\leq i\leq j\leq n$$$.

Input:

The first line contains an integer $$$n \left(3\leq n \leq5.10^5\right)$$$.

The second line contains $$$n$$$ space-separated integers $$$a_1,a_2,...,a_n \left(-10^3\leq a_i \leq10^3\right)$$$.

Output:

The maximum value of $$$P$$$.