Description

在上次中忍考试中小李的腿受了重伤，幸好在纲手婆婆（不对，是纲手公主...）的医治下又重新站了起来。为了有一天能成为像凯老师那样强大的体术忍者，他决定继续修行。一天，他来到了木叶村旁的山脚下开始自己的修炼，在他面前有N根石柱(1<=N<=10^5)，从左到右排列，编号从1到N，编号为i的石柱高度为H(i) ( 1<=H(i)<=10^5)。

起初，小李所站的位置高度为0。每次小李跳到下一根石柱上。假设小李在第K根石柱上，他现在体力为E，下一步他将跳到第K+1根石柱上，他将会得到或失去正比于与H(K+1)与E之差的体力。如果(H(K+1)>E)那么小李就失去H(K+1)-E点体力，否则他将得到E-H(k+1)点体力。

小李的目标是到达第N根石柱（“木叶的苍蓝猛兽”正在那里等着他），在这个过程中，小李的体力不能为负数，现在请问小李的初始体力最少为多少时能保证到达第N根石柱？

燃烧吧，青春！木叶的莲华将会再次绽放。

Format

Input

第一行输入一个整数N，表示一共有N个整数。

第二行是N个空格分隔的整数，H1,H2,H3,...,Hn代表石柱的高度。

Output

输出一个单独的数表示小李通过这些石柱所需的最小体力。

Samples

5
3 4 3 2 4

4

3
4 4 4

4

3
1 6 4

3

Hint

① 你可以认为小李初始时站在编号为0的石柱上，石柱的高度为0，接下来他将跳到编号为1的石柱上

②如果恰好落在第n根石柱上时体力为负同样是不合法的