Maximum Stock Profit Queries

You are given a list of daily stock prices and several queries. Each query provides two integers, l and r (1-indexed), representing the starting and ending day of a period. Your task is to determine the maximum profit achievable during that period by buying and selling the stock.

The profit for a given query is calculated as:

$$\max_{l \leq i < j \leq r} (prices[j] - prices[i])$$

If no profit can be made (i.e. if the best possible profit is negative or there is only one day in the range), output 0.

inputFormat

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

• The first line contains an integer n, the number of days.
• The second line contains n space-separated integers representing the stock prices for each day.
• 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, the indices defining the query range (1-indexed).

outputFormat

For each query, print the maximum profit on a separate line to stdout. If no profit is possible, print 0.

## sample

6
7 1 5 3 6 4
2
1 6
2 4

5
4

</p>