Description

HKE has recently been keen on studying sequences, and once he discovered an interesting problem:

For a sequence $A_1,A_2,\cdots,A_n$, find two indices $i, j$ ($1\le i<j\le n$) such that $A_j-A_i$ is maximized.

Given this sequence, please find the maximum value of $A_j-A_i$.

Input Format

The first line contains a positive integer $n$. The next $n$ lines each contain one integer. The integer on the $(i + 1)$-th line is $A_i$.

Output Format

One line, the maximum value of $A_j-A_i$.

10
1
3
4
6
7
9
10
1
2
9

9

Hint

Constraints

• For $30\%$ of the testdata, $n\le1000$.
• For $70\%$ of the testdata, $n\le10^5$.
• For $100\%$ of the testdata: $2\le n\le 10^6$, and $A_i$ is within the int range.

Translated by ChatGPT 5