Maximum Difference in a Sequence

HKE is fascinated by numerical sequences. One day, he encountered an interesting problem: given a sequence \(A_1, A_2, \ldots, A_n\), find two indices \(i\) and \(j\) (with \(1 \le i < j \le n\)) such that the difference \(A_j - A_i\) is maximized.

For example, in the sequence [1, 2, 3, 4, 5], the maximum difference is \(A_5 - A_1 = 5 - 1 = 4\).

inputFormat

The input begins with an integer \(n\) indicating the number of elements in the sequence. The next line contains \(n\) space-separated integers \(A_1, A_2, \ldots, A_n\).

outputFormat

Output a single integer: the maximum value of \(A_j - A_i\) for all pairs \((i, j)\) satisfying \(1 \le i < j \le n\).

sample

5
1 2 3 4 5

4