403669: GYM101237 F Just Another Sequence Problem

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Just Another Sequence Problemtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

ExamplesInput
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.

加入题单

上一题 下一题 算法标签: