F. Just Another Sequence Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given a sequence (A1, A2, ..., AN) consisting of integers. Your task is to split this sequence into contiguous non-empty parts such that the value S1·S2 + S2·S3 + ... + Sk - 1·Sk is as large as possible, where k is the total number of parts and Si is the sum of all integers in i-th part (in the order from left to right).

Note that if k = 1, this value is assumed to be equal to zero.

Input

The first line contains the integer N, the length of the sequence (1 ≤ N ≤ 2000).

The second line contains integers A1, A2, ..., AN separated by spaces ( - 1000 ≤ Ai ≤ 1000).

Output

Output the maximal possible value of S1·S2 + S2·S3 + ... + Sk - 1·Sk.

Examples
Input
6
2 -1 4 3 -1 0
Output
13
Note

In the example case, the optimal partition is (2,  - 1), (4), (3), ( - 1, 0), it produces the value S1·S2 + S2·S3 + S3·S4 = 1·4 + 4·3 + 3·( - 1) = 13.