Description

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

起初，小李所站的位置高度为0。假设小李当前体力为E，当他跳到第i 根石柱上时，他将会得到或失去值为H(i) 与E 之差的绝对值 的体力。如果H(i) > E，那么小李就失去H(i) - E 点体力，否则他将得到E - H(i) 点体力。

小李的目标是到达第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根石柱上时体力为负同样是不合法的