William is given an array of integers . He then must pick one contiguous segment and multiply all values on that segment by .
His goal is such that after modifying this segment, the sum of the prefix sums is minimized. This value can be represented as:
Output the minimal value attainable under the given terms.
The first line consists of a single integer .
The next line contains space-separated integers .
Subtask 1 [20%]
Subtask 2 [80%]
No further constraints.
Output a single integer, the minimal value attainable of the expression outlined above.
Sample Input 1
4 1 -2 100 -5
Sample Output 1
Explanation for Sample 1
If the segment was modified our array will become: .
The prefix sum of the modified array is:
Thus the answer would be the sum of the prefix sum of all elements:
The value is the minimum attainable answer.
Sample Input 2
5 -10 7 -2 -2 10
Sample Output 2