Maximum Difference in an Array

Given an array of integers \(A\) of length \(n\), find the maximum difference between any two elements such that the larger element comes after the smaller one. In other words, you are to find the maximum value of \(A[j] - A[i]\) where \(0 \le i < j < n\). If no such pair exists (for example, if the array is empty, has only one element, or is non-increasing), output \(-1\).

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(n\) which represents the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output via standard output (stdout) a single integer representing the maximum difference \(A[j] - A[i]\) for any pair with \(i < j\). If no such pair exists, output \(-1\).

7
2 3 10 6 4 8 1

8