717. Reverse Subarray To Maximize Array Value

0

Hard

Given an array of integers called nums, the value of this array is defined as the sum of the absolute differences between consecutive elements. You are allowed to select a subarray of nums and reverse it. However, you can only perform this operation once. Find the maximum possible value of the final array.

Input Format

The first line of input contains the size of the array. The second line contains the elements of the array.

Output Format

Output the maximum possible value of the final array.

Example

Input

5
2 3 1 5 4

Output

10

Constraints

1 <= nums.length <= 3 * 10^4
-10^5 <= nums[i] <= 10^5

Loading...

View Submissions

Console