Description

The mountain path he walks on can be seen as a number sequence $P_i$ of length $n$, where $P_i$ means the height at position $i$ is $P_i$.

A continuous segment with strictly increasing heights when walking from a lower place to a higher place is called one ascent.

To work out, he wants to walk an ascent with as large a height difference as possible.

The height difference of a segment is defined as the difference between the end point and the start point of this segment.

You need to find the maximum height difference he can achieve by walking on a segment of the path.

Input Format

The first line contains an integer $n$, representing the length of the path.

The second line contains $n$ integers $P_i$, where $P_i$ represents the height at position $i$.

Output Format

Output one integer on a single line, representing the maximum height difference.

If the entire path does not contain any ascent, output 0.

5
1 2 1 4 6

5

8
12 20 1 3 4 4 11 1

8

6
10 8 8 6 4 3

0

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 1000$, $1 \le P_i \le 1000$.

Notes

Translated from COCI2010-2011 CONTEST #6 T2 USPON。

Translated by ChatGPT 5