Given an array $$A$$ of $$N$$ integers. Now, you have to output the sum of unique values of the maximum subarray sum of all the possible subarrays of the given array $$A$$.
Note: Subarray means contiguous elements with atleast one element in it.

Input Format

The first line of the input contains a single integer $$N$$, the total number of elements in array $$A$$.
The next line of the input contains $$N$$ space-separated integers representing the elements of the array.

Output Format

The only single line of the output should contain a single integral value representing the answer to the problem.

Constraints

$$1 \le N \le 2000$$
$$0 \le |A_i| \le 10^9$$