Absolute Difference in Subarray Extremes

Given an array of integers and a number of queries, for each query you are required to find the absolute difference between the maximum and minimum values in a subarray. For a subarray specified by indices \(l\) and \(r\), the answer is calculated as

\( |\max\{a_l, a_{l+1}, \dots, a_r\} - \min\{a_l, a_{l+1}, \dots, a_r\}| \)

This problem requires reading input from stdin and writing the results to stdout in the specified format.

inputFormat

The first line contains an integer (n), the number of elements in the array. The second line contains (n) space-separated integers representing the array. The third line contains an integer (q), the number of queries. Each of the following (q) lines contains two integers (l) and (r), representing the indices (1-indexed) that specify the subarray.

outputFormat

For each query, output a single line containing the absolute difference between the maximum and minimum values in the subarray defined by the query.## sample

7
1 5 2 4 6 3 7
3
1 3
4 7
2 5

4
4
4