该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

游戏中一共有$N$个建筑，从左往右排列，编号为 0 的建筑高度为 0 个单位，编号为 $i$ 的建筑高度为$H_i$个单位。 起初，汉娜在编号为 0 的建筑物处，每一步，她会飞到下一个（右边）建筑，假设汉娜在第 $K$ 个建筑，且她现在的能量值是 $E$，下一步她将跳到第 $K+1$ 个建筑，如果$H_{k + 1}$ > $E$，那么汉娜就失去$H_{k + 1}$ $-$ $E$的能量值，否则她将得到$E$ $-$ $H_{k + 1}$的能量值. 目标是到达第$N$个建筑，在这个过程中，能量值不能为负值，问汉娜以多少的能量值开始游戏，才可以保证完成游戏？

Format

Input

第一行输入表示一共有 $n$ $(1\leq n \leq 10^5)$座建筑.

第二行是 $n$ 个空格分隔的整数, $H_1,H_2,...H_n$$(1 \leq H_i \leq 10^5)$代表建筑的高度.

Output

输出一个单独的数表示完成游戏所需的最少单位的初始能量.

Samples

5
3 4 3 2 4

4

3
1 6 4

3

Limitation

1s, 1024KiB for each test case.