Maximum Difference in Array

You are given an array of integers. Your task is to compute the maximum difference between any two elements in the array such that the larger element comes after the smaller one. If no such pair exists (for instance, when the array is empty or has only one element, or it is sorted in non-increasing order), the answer should be 0.

Hint: Make sure to update the minimum element seen so far while traversing the array.

Mathematically, if the array elements are represented as \(a_1, a_2, \dots, a_n\), you need to find the maximum value of \(a_j - a_i\) subject to \(i < j\). If no valid \(i, j\) exists, output 0.

inputFormat

The input is given via standard input and consists of two lines. The first line contains a single integer \(n\) which represents the number of elements in the array. The second line contains \(n\) space-separated integers representing the array elements. If \(n = 0\), the second line may be empty.

outputFormat

Output a single integer on standard output: the maximum difference between any two elements where the larger comes after the smaller. If there is no valid pair, output 0.

5
1 2 90 10 110

109