Maximum Height Difference

The task is to determine, for each specified range query in a series of test cases, the maximum height difference between buildings. For a given query with bounds (L) and (R), calculate the difference using the formula: (\text{difference} = \max(\text{heights}[L,R]) - \min(\text{heights}[L,R])). Each test case starts with an integer denoting the number of buildings, followed by the list of their heights, and then a number of queries. For every query, you are required to output the maximum difference between any two buildings within the specified range. The input is read from standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

Input is provided via stdin. The first line contains a single integer (T), the number of test cases. For each test case, the input format is as follows:

1. An integer (N) representing the number of buildings.
2. A line containing (N) space-separated integers representing the heights of the buildings.
3. An integer (Q) representing the number of queries.
4. (Q) lines, each containing two space-separated integers (L) and (R) (1-indexed), pinpointing the range for which you must compute (\max(heights[L,R]) - \min(heights[L,R])).

outputFormat

Output the maximum height difference for each query on a new line. All results should be printed to stdout in the order in which the queries appear in the input.## sample

2
5
1 3 5 7 9
2
1 3
2 5
4
4 8 2 10
1
1 4

4
6
8