Beauty of Subarray

You are given an integer array \(A\) of size \(n\) and \(q\) queries. Each query consists of two integers \(L\) and \(R\) (1-indexed) representing a subarray \(A[L \ldots R]\). The beauty of a subarray is defined as the difference between the maximum and minimum element in that subarray, i.e.,

\(Beauty = \max\{A[i] : L \le i \le R\} - \min\{A[i] : L \le i \le R\}\)

Your task is to compute and output the beauty for each query.

inputFormat

The first line contains an integer \(n\) denoting the number of elements in the array. The second line contains \(n\) space-separated integers representing 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 space-separated integers \(L\) and \(R\) representing a query.

outputFormat

For each query, output the beauty of the subarray (i.e., the difference between the maximum and minimum elements) on a new line.

## sample

1
5
1
1 1

0

</p>