题目描述

$Oxy$ 参加了最新一届的极限探险大师活动（$\textit{Master Explore Xtreme}$）！

在本届活动中，主办方为探险家们准备了一座结构复杂的空中遗迹，而 $Oxy$ 需要先通过"阶梯秘境"后才能进入遗迹！ 这个秘境总共有 $n$ 处落脚点，从出发点到终点的第 $i$ 处落脚点的高度为 $h_i$ 米，最后一处落脚点视为终点。

$Oxy$ 需要从地面出发（高度为 $0$ 米），依次跳到第 $1, 2, \dots, n$ 处落脚点。 由于直接挑战过于困难，他打算购买一件古文明遗物——"能量缓冲靴"。 这双靴子可以储存能量，上限为 $E$ 点。出发前，能量会自动充满，即初始能量为 $E$ 点。

$Oxy$ 跳跃时，假设当前所处的高度为 $H_1$ 米，目标落脚点所处的高度为 $H_2$ 米。

• 若 $H_1 > H_2$：靴子会储存 $H_1 - H_2$ 点能量，若跳跃后靴子总存储的能量超过 $E$ 点，多余的能量会被浪费；
• 若 $H_1 \leq H_2$：靴子会消耗 $H_2 - H_1$ 点能量，若跳跃前靴子剩余的能量不足 $H_2 - H_1$ 点，则挑战会直接失败。

随着能量储存上限的增大，靴子的费用也会迅速增长。$Oxy$ 想知道，$E$ 至少为多少时，才能支撑他到达秘境的终点？

输入格式

第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$) — 落脚点的数量。

第二行包含 $n$ 个整数 $h_1, h_2, \cdots, h_n$ ($0 \leq h_i \leq 10^9$) — 每个落脚点的高度。

输出格式

输出一个整数，表示能支撑 $Oxy$ 到达终点所需的最小的 $E$。

样例

3
5 3 10

10

1
10

10