Question
Sequence Spin
You have a list A of N numbers. In a single operation, you can select any contiguous segment of the list and rotate it left or right by any number of positions. After performing exactly one such operation, determine the maximum possible value of AN - A1.
Input
The first line of the input contains a single integer N.
The second line of the input contains N space-separated integers.
The second line of the input contains N space-separated integers.
Output
Print the maximum value of AN - A1 after performing the above operation exactly once.
Example
Sample Input
4
2 1 8 1
Sample Output
7
Explanation
Select left as 0 and right as 3
After rotation by one position to the right the array will look like
1 2 1 8
4
2 1 8 1
Sample Output
7
Explanation
Select left as 0 and right as 3
After rotation by one position to the right the array will look like
1 2 1 8