Maximum Difference

Given an array of integers, your task is to determine the maximum difference between two elements such that the larger element appears after the smaller one. In mathematical terms, you are to find the maximum value of \(a_j - a_i\) for all indices \(i, j\) satisfying \(0 \le i < j < n\) where \(n\) is the number of elements in the array. If no valid pair exists (for example, when the array has fewer than 2 elements or when no element is larger than a previous one), output 0.

inputFormat

The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

Output a single integer which is the maximum difference as defined above. If no such difference exists, output 0.

5
1 2 90 10 110

109