对于一段序列，定义这段序列的权值为这段序列的极差，即序列的最大值与最小值之差。

给定一个序列 $a$ ，你可以将它划分成任意段连续的序列，求出每一段的权值和的最大值

输入格式

第一行输入一个整数 $n$ , 表示序列的长度 $( 1 \leq n \leq 10^6 )$。

第二行输入 $n$ 个整数 $a_1 , a_2 , a_3 , \dots , a_n$ 表示给定的序列 。 $( -10^9 \leq a_i \leq 10^9 )$

输出格式

输出一行一个整数表示每一段的权值和的最大值。

样例输入

5
9 6 1 8 8 

样例输出

10

样例解释

划分成 $[9,6] , [1,8,8]$的权值最大