The maximum difference for a pair of elements in some array a is defined as the largest difference between any a[i] and a[j] where i < j and a[i] < a[j]. Create a Function maxDifference to find the maximum difference from array a.

Output Format

Your maxDifference function should return the maximum difference in a.

Sample Input

7
2
3
10
2
4
8
1

Sample Output

8

Sample Input

6
7
9
5
6
3
2

Sample Output

2

Explanation

Sample Case 0: n = 7, a = {2, 3, 10, 2, 4, 8, 1}

As a[2] = 10 is largest element in the array, we must find the smallest a[i] where 0 ≤ i < 2. This ends up being 2 at index 0.

We then calculate the difference between the two elements: a[2] − a[0] = 10 − 2 = 8, and return the result (8).

Note: While the largest difference between any two numbers in this array is 9 (between a[2] = 10 and a[6] = 1), this cannot be our maximum difference because the element having the smaller value (a[6]) must be of a lower index than the element having the higher value (a[2]). As 2 is not less than 6, these elements cannot be used to calculate our maximum difference.

Sample Case 1: n = 6, a = {7, 9, 5, 6, 3, 2}

The maximum difference returned by our function is a[1] − a[0] = 9 − 7 = 2, because 2 is the largest difference between any a[i] and a[j] satisfying the conditions that a[i] < a[j] and i < j.

Note: You could use any programming language you like. e.g. PHP , Javascript, Ruby , Java , C , C++ etc.