Sum of Maximum and Minimum in Subarrays

You are given an array of integers \(a\) and a list of queries. For each query, represented as a pair of indices \(L\) and \(R\) (0-indexed), compute the sum of the maximum and minimum values in the subarray \(a[L \ldots R]\). That is, for each query calculate:

\(\text{answer} = \max_{L \le i \le R} a_i + \min_{L \le i \le R} a_i\)

Print each answer on a new line.

Note: The input is provided via stdin and your output should be written to stdout.

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 \(a\).

The third line contains an integer \(q\), the number of queries.

Each of the next \(q\) lines contains two space-separated integers \(L\) and \(R\) (0-indexed) defining a query.

outputFormat

For each query, output a single line containing the sum of the maximum and minimum values of the subarray from index \(L\) to \(R\) (inclusive).

## sample

5
1 3 -1 5 4
3
0 2
1 3
0 4

2
4
4

</p>