Performance Score

You are given a list of scores of n challenges and a number of queries. For each query, you are provided with two integers, l and r, representing the start and end indices (1-indexed) of a range of challenges. Your task is to compute the performance score for each query, which is defined as:

\(\text{performance} = \max(s_l, s_{l+1}, \dots, s_r) - \min(s_l, s_{l+1}, \dots, s_r)\)

Output the computed performance score for every query on a separate line.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n representing the number of scores.
• The second line contains n space-separated integers that represent the scores.
• The third line contains an integer q representing the number of queries.
• The following q lines each contain two space-separated integers l and r representing a query.

outputFormat

For each query, output one line to stdout containing a single integer: the performance score for that query.

## sample

5
50 80 90 40 60
3
1 3
2 5
1 5

40
50
50

</p>