Crossing the Buildings

Problem Description

There are $N+1$ buildings, numbered $0$ to $N$ from left to right. Building $0$ has height $0$, and building $i$ has height $H(i)$.

You start from building $0$ with initial energy $E$, and each step you jump to the next building on the right. Suppose you are currently at building $k$ with energy $E$, and you jump to building $k+1$:

• If $H(k+1) > E$, you lose $H(k+1) - E$ energy;
• Otherwise you gain $E - H(k+1)$ energy.

Your energy must never drop below $0$ during the whole process. Find the minimum initial energy (rounded up) required to successfully reach building $N$.

Input Format

The first line contains an integer $N$.

The second line contains $N$ space-separated integers $H(1), H(2), \dots, H(N)$, the heights of the buildings.

Output Format

Output one integer, the minimum initial energy required (after rounding up).

Sample Input

5
3 4 3 2 4

Sample Output

4

Constraints

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