Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:1024 MB

#709. 最大权值划分

附加文件 统计

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

给定一个序列 $ 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]$的权值最大