Range Height Difference

You are given an array of integers representing the heights of books on a shelf and several queries. Each query is specified by two 1-based indices. For each query, you need to determine the difference between the maximum and minimum heights among the books in that range.

Input Format:

• The first line contains an integer n representing the number of books.
• The second line contains n integers representing the heights of the books.
• The third line contains an integer q that specifies the number of queries.
• The next q lines each contain two integers, the starting and ending indices (1-based) of the query.

Output Format:

• Print a single line with q integers separated by a space. Each integer is the difference between the maximum and minimum heights in the corresponding query.

Mathematical Formulation:

For each query \( (l, r) \), compute: \[ \text{result} = \max(\{h_i : l \le i \le r\}) - \min(\{h_i : l \le i \le r\}) \]

inputFormat

The input is read from standard input (stdin) and is structured as follows:

• The first line contains an integer n (the number of books).
• The second line contains n space-separated integers, the heights of the books.
• The third line contains an integer q (the number of queries).
• Each of the next q lines contains two space-separated integers indicating the start and end indices (1-based) of each query.

outputFormat

The output is written to standard output (stdout) as a single line with q space-separated integers. Each integer corresponds to the difference between the maximum and minimum values in the subsequence defined by the query.

## sample

5
2 5 3 8 6
3
1 3
2 4
1 5

3 5 6

</p>