7886 - 最大距离 15'

通过次数

91

提交次数

155

时间限制 : 1 秒
内存限制 : 512 MB

在数列 a_1, a_2, ..., a_n中,定义两个元素 a_ia_j 的距离为 |i-j|+|a_i-a_j|,即元素下标的距离加上元素值的差的绝对值,其中 |x| 表示 x 的绝对值。 
给定一个数列,请问找出元素之间最大的元素距离。

输入

输入的第一行包含一个整数 n。 
 第二行包含 n 个整数 a_1, a_2, ..., a_n,相邻的整数间用空格分隔,表示给定的数列。

输出

输出一行包含一个整数,表示答案。

样例

输入

5
9 4 2 4 7

输出

9

提示

评测用例规模与约定 
对于100\%的数据,1 \le n,a_i \le 10000

来源

蓝桥杯官方C组省内模拟赛重现(民间数据)