Pref Suff Chmyaaax Diff
You are given an array consisting of integers. You need to perform the following steps in the given order:
Take some index .
Divide the array into two parts: and .
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 . 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 .
Input
In the first line, there is one integer — the number of elements in the array .
In the second line, there are integers — the elements of the array.
Output
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.
Examples
Note
In the first sample, the only way to divide the array is to take , 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 .
In the second sample, there are ways of performing operations:
-> -> the result is ;
-> -> the result is ;
-> -> ;
-> -> ;
-> -> ;
-> -> ;
-> -> ;
-> -> ;
-> -> ;
-> -> .
As we can notice, the maximum possible value here is , which can be obtained by taking 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.
Scoring
( points): ;
( points): all elements of the array are equal ( for all );
( points): all elements of the array are positive ( for all );
( points): the array is non-decreasing ( for all );
( points): ;
( points): ;
( points): no additional constraints.