Enming has been bullying soupy boy by using his height advantage, always patting his head and calling him small, now soupy boy, who wields the power of creating the problems for Enming's quiz, uses it to get revenge.
Surprisingly, Enming has been getting better at coding! Thus, soupy boy now wants to give him a challenge.
Enming Is given an array ~A~ consisting of ~n~ integers, he needs to find the maximum value of the following expression:
~|A_i - A_j| + |i - j|~
where ~0 \le i, j < n~ and ~A_i, A_j~ are the array elements.
First line contains the integer ~n~ the number of elements in the array.
Second line contains ~n~ space separated integers ~A_i~.
Print the maximum value of the above given expression.
- ~2 \le n \le 10^6~
- ~1 \le A_i \le 10^9~
Sample Input 1
3 1 1 1
Sample Output 1
Explanation Of Sample 1
If we choose ~i=0~ and ~j=2~, then we get the maximum value of ~|1 - 1| + |0 - 2| = 2~.
Sample Input 2
4 1 2 3 1
Sample Output 2
Explanation Of Sample 2
If we choose ~i=0~ and ~j=2~, then we get the maximum value of ~|1 - 3| + |0 - 2| = 4~.