Maximum Difference

You are given a sequence of integers. Your task is to find the maximum difference between two elements such that the larger element appears after the smaller one in the sequence.

If no such pair exists, simply output -1.

Note: The difference is computed as a[j] - a[i] for some indices i < j. If no valid pair exists, output -1.

Example:
For the sequence [1, 2, 90, 10, 110, 5], the maximum difference is 110 - 1 = 109.

This problem is designed to test your ability to optimize a simple search by scanning the input sequence while tracking the minimum element seen so far.

inputFormat

The input is provided via standard input (stdin). The first line contains a single integer n, which is the number of elements in the sequence. The second line contains n space-separated integers representing the sequence.

outputFormat

Output a single integer to standard output (stdout) representing the maximum difference between two elements where the later element is larger than the former. If no such pair exists, output -1.## sample

6
1 2 90 10 110 5

109