Given an array of integers where . Each element in should be assigned into a group while satisfying the following rules.
Each element belongs to exactly one group.
If and where belongs to the same group, then where also belongs to the same group as and .
There is at least one pair of elements that belong to a different group.
Let denotes the group ID of element . The cost of a group is equal to the sum of all elements in that belong to that group.
Two different group IDs, and (where ), are adjacent if and only if is either or for every . Finally, the value of two group IDs and is defined as the absolute difference between and .
Your task in this problem is to find a group assignment such that the largest value between any pair of adjacent group IDs is maximized; you only need to output the largest value.
For example, let . There are ways to assign each element in into a group in this example; some of them are shown as follows.
. There are pairs of group IDs that are adjacent and their values are:
,
, and
.
The largest value in this group assignment is .
. There are pairs of group IDs that are adjacent and their values are:
, and
.
The largest value in this group assignment is .
The other group assignments are: , , , , , and . Among all possible group assignments in this example, the maximum largest that can be obtained is from the group assignment .
输入格式
Input begins with a line containing an integer () representing the number of elements in array . The next line contains integers () representing the array .
输出格式
Output contains an integer in a line representing the maximum possible largest that can be obtained from a group assignment.
样例
样例输入 1
4
100 -30 -20 50
样例输出 1
150
样例输入 2
5
12 7 4 32 9
样例输出 2
46
样例输入 3
6
-5 10 -5 45 -20 15
样例输出 3
70
数据范围与提示
Explanation for the sample input/output #2
The maximum possible largest of can be obtained from the group assignment . The value of the only adjacent group IDs is: .
Explanation for the sample input/output #3
The maximum possible largest of can be obtained from the group assignment . The values of any two adjacent group IDs are: , , and .
