翻越建筑

题目描述

有 $N+1$ 座建筑，从左到右编号为 $0$ 到 $N$。第 $0$ 座建筑高度为 $0$，第 $i$ 座建筑高度为 $H(i)$。

你从第 $0$ 座建筑出发，初始能量为 $E$，每一步都跳到右边相邻的下一座建筑。假设你当前在第 $k$ 座建筑、能量为 $E$，跳到第 $k+1$ 座建筑时：

• 若 $H(k+1)>E$，则失去 $H(k+1)-E$ 点能量；
• 否则获得 $E-H(k+1)$ 点能量。

整个过程中能量不能为负。求能够顺利到达第 $N$ 座建筑所需的最小初始能量（向上取整）。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个用空格分隔的整数 $H(1),H(2),\dots,H(N)$，表示各建筑的高度。

输出格式

输出一个整数，表示所需的最小初始能量（向上取整后的结果）。

样例输入

5
3 4 3 2 4

样例输出

4

数据范围

• $1\le N\le 10^5$
• $1\le H(i)\le 10^5$