Maximum Difference in List

You are given a list of integers and your task is to determine the maximum difference between any two elements such that the larger element comes after the smaller one in the list. In other words, for a given sequence \(a_1, a_2, \ldots, a_n\), find the maximum value of \(a_j - a_i\) for any indices \(i < j\) where \(a_j > a_i\). If no such pair exists, output -1.

Note: The input list may contain negative numbers as well. The goal is to perform the computation in an efficient manner.

Examples:

• For the list [7, 1, 5, 4, 6, 3], the answer is 5.
• For the list [1, 2, 90, 10, 110], the answer is 109.
• For the list [5, 4, 3, 2, 1], the answer is -1.

inputFormat

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

outputFormat

Output a single integer, the maximum difference \(a_j - a_i\) with \(j > i\) where \(a_j > a_i\). If no such pair exists, output -1.

6
7 1 5 4 6 3

5