Maximum Difference in Subarray Queries

You are given an array A of N integers and Q queries. Each query specifies a subarray by its 1-indexed starting index L and ending index R. For each query, your task is to compute the maximum difference between any two elements in the subarray A[L...R] (i.e. the difference between its maximum and minimum elements).

The difference is defined as:

[ \text{max_difference} = \max_{L \le i \le R} A_i - \min_{L \le i \le R} A_i ]

It is guaranteed that the array indices provided in the queries are valid. Use efficient implementation techniques if necessary as the size of the array or number of queries can be large.

inputFormat

The first line contains an integer N representing the number of elements in the array.

The second line contains N space-separated integers, the elements of the array A.

The third line contains an integer Q, the number of queries.

Each of the following Q lines contains two integers L and R (1-indexed) representing the subarray bounds.

Input is to be read from standard input (stdin).

outputFormat

For each query, print a single integer on a new line representing the maximum difference in the given subarray.

Output should be written to standard output (stdout).

## sample

5
1 5 3 2 4
3
1 3
2 5
1 5

4
3
4

</p>