对于一段序列,定义这段序列的权值为这段序列的极差,即序列的最大值与最小值之差。
给定一个序列 $ 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]$的权值最大