Maximum Difference in Array

Given an array of integers, find the maximum difference between two elements such that the smaller element appears before the larger element in the array. Formally, for an array \(a_0, a_1, \dots, a_{n-1}\), determine \(\max_{0 \le i < j < n} (a_j - a_i)\). If no such pair exists (for example, when the array is empty or has less than two elements), output 0.

It is guaranteed that the required answer will fit into a 64-bit signed integer.

inputFormat

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

outputFormat

Output a single integer which is the maximum difference between two elements where the smaller element appears before the larger one.

7
2 3 10 6 4 8 1

8