Pref Suff Chmyaaax Diff#11705
You are given an array a_1, a_2, \dots, a_n consisting of integers. You need to perform the following steps in the given order:
Take some index (1 \le k \le n - 1).
Divide the array into two parts: a_1, a_2, \dots, a_k and a_{k+1}, a_{k+2}, \dots, a_n.
Remove one element from both parts.
Let be the sum of elements of the first resulting part and let be the sum of elements of the second one. You need to find the maximum possible value of |c - d|. In other words, your task is to find the maximum possible difference between sums of the resulting parts after performing these steps.
You can assume that the sum of elements of the empty part is .
In the first line, there is one integer (2 \le n \le 10^5) — the number of elements in the array .
In the second line, there are integers a_i (-10^3 \le a_i \le 10^3) — the elements of the array.
In the first and only line, you need to output a single integer — the maximum possible difference between sums of the resulting parts after performing such steps.
Example
Example 1
Example 2
Example 3
Example 4
Example 5
In the first sample, the only way to divide the array is to take k = 1, i.e. make two subarrays and . Since they both consist of one element, the only way to remove one element from each subarray is to remove both of them. This way, the subarrays become empty, their sums become , thus the answer is |0 - 0| = 0.
In the second sample, there are ways of performing operations:
[2], [-5, 4, -7] — [], [4, -7] — the result is |0 - (4 + (-7))| = |0 - (-3)| = 3;
[2], [-5, 4, -7] — [], [-5, -7] — the result is |0 - (-5 + (-7))| = 12;
[2], [-5, 4, -7] — [], [-5, 4] — |0 - (-5 + 4)| = 1;
[2, -5], [4, -7] — [-5], [-7] — |(-5) - (-7)| = 2;
[2, -5], [4, -7] — [-5], [4] — |(-5) - (4)| = 9;
[2, -5], [4, -7] — [2], [-7] — |(2) - (-7)| = 9;
[2, -5], [4, -7] — — |(2) - (4)| = 2;
[2], [-5, 4, -7] — [], [4, -7] — |0 - (4 + (-7))| = 3;
[2], [-5, 4, -7] — [], [-5, -7] — |0 - (-5 + (-7))| = 12;
[2], [-5, 4, -7] — [], [-5, 4] — |0 - (-5 + 4)| = 1.
As we can notice, the maximum possible value here is , which can be obtained by taking k = 2 and leaving from the first resulting subarray and from the second one.
In the third sample, it does not matter how do we divide the array or what element to we remove from them — the sum of any of the resulting subarrays will always be , as well as the difference between them.
( points): n \le 3;
( points): all elements of the array are equal (a_i = a_j for all 1 \le i, j \le n);
( points): all elements of the array are positive (a_i > 0 for all 1 \le i \le n);
( points): the array is non-decreasing (a_i \le a_j for all 1 \le i < j \le n);
( points): n \le 300;
( points): n \le 2000;
( points): no additional constraints.