Maximum Climb

Interview

Time limit1sMemory limit1024 MB

Summary

Given N course heights, find the largest difference between the end and start of a run of consecutive strictly increasing heights.

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

One of the most important features of ski, running, and cycling marathons is the course elevation profile, especially its maximum climb.

The elevation profile gives the heights $H_1$ , $H_2$ , $\dots$ , $H_N$ of $N$ course points. A climb is a sequence of consecutive points where each point is strictly higher than the one before it. The height of a climb is the difference between the heights at its start and end.

Write a program that finds the maximum climb height in the given profile.

Input

The first line contains the number of points $N$ ( $1 \le N \le 50\,000$ ). The next $N$ lines contain the integer heights $H_i$ ( $0 \le H_i \le 1\,000\,000$ ) of the points in order from start to finish, one per line.

Output

Print one integer: the maximum climb height, that is, the maximum difference $H_i - H_j$ over $j \le i$ with $H_j < H_{j+1} < \dots < H_i$ . If there is no climb at all, print 0. (haha :)

Examples1

Example 1
Input
```
7
2
1
3
2
4
5
3
```
Expected output
```
3
```