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≤N≤2000
0≤|Ai|≤109
Following are the possible number of subarrays and their respective maximum subarray sums:
[5]=[5]=5
[5,−2]=[5]=5
[5,−2,7]=[5,−2,7]=10
[5,−2,7,−3]=[5,−2,7]=10
[−2]=[−2]=−2
[−2,7]=[7]=7
[−2,7,−3]=[7]=7
[7]=[7]=7
[7,−3]=[7]=7
[−3]=[−3]=−3
5+10+(−2)+7+(−3)=17
