## William and Summation

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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.

#### Input Specification

The first line consists of a single integer .

The next line contains space-separated integers .

No further constraints.

#### Output Specification

Output a single integer, the minimal value attainable of the expression outlined above.

#### Sample Input 1

4
1 -2 100 -5

#### Sample Output 1

-207

#### 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

-78