Maximum Difference

You are given an array of integers and your task is to find the maximum difference between two elements such that the larger element comes after the smaller element. Formally, for an array \(a_0, a_1, \dots, a_{n-1}\), you need to compute

[ \max_{0 \le i < j < n} (a_j - a_i) ]

if there exists any pair \((i, j)\) with \(a_j > a_i\). If no such pair exists, output -1. This problem challenges you to come up with an efficient \(O(n)\) solution by scanning the array while keeping track of the minimum value encountered so far.

inputFormat

The first line contains an integer T representing the number of test cases. Each test case is described in two lines:

• The first line contains an integer N, the number of elements in the array.
• The second line contains N space-separated integers, the elements of the array.

outputFormat

For each test case, print a single line with the maximum difference. If no valid pair exists, output -1.

## sample

4
5
1 2 90 10 110
4
15 12 10 5
5
1 2 3 4 5
4
1 1 1 1

109
-1
4
-1

</p>