You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

$zxc$颇有冒险精神，正在玩一个古老的基于$D0S$的游戏，游戏中有$N$座山峰，从1到$N$编号，从左到右排列,$zxc$起始在0号位置，高度为0个单位，编号为i的山峰的高度为$H(i)$个单位,每一步，她跳到下一个(右边)山峰。假设$zxc$在第$k$个山峰，且它现在的能量值是$E$,下一步她将跳到第个$k$+1山峰,她将会得到或者失去正比于与$H(k+1)$与$E$之差的能量,如果 $H(k+1)> E$ 那么$zxc$就失去$H(k+1)-E$的能量值，否则她将得到$E-H(k+1)$的能量值,游戏目标是到达第个$N$山峰，在这个过程中，能量值不能为负数个单位。现在的问题是$zxc$想知道以多少能量值开始游戏，才可以保证成功完成游戏。

输入格式

输入两行，第一行为$n$，表示有$n$座山峰。

第二行是$n$个数字，表示每一座山峰的高度。

输出格式

输出$zxc$初始能量的最小值。

样例1：

5
3 4 3 2 4

4

样例2：

3
1 6 4

3

样例 1 解释

一共5座山峰，分别为3,4,3,2,4，起始E为4，跳到第一座E增加4+（4-3）=5，第二座5+（5-4）=6，第三座6+（6-3）=9，第四座9+(9-2)=16,第五座16+(16-4)=28。

如果小于4，比如为3，到第4座的时候她的能量已经变成0，无法完成。

对于 $100\%$ 的数据，$1 \le n hi \le 10^6$。