Maximum Stock Profit Query

You are given an array of stock prices over consecutive days. You are also provided with multiple queries. Each query is represented by two indices i and j (0-indexed) which define a subarray of the prices: prices[i...j]. For each query, determine the maximum profit that can be achieved by buying on one day and selling on a later day within that subarray. If no profit is possible, output 0.

The profit for a buy at day i and sell at day j is given by the formula \[ \text{profit} = p_{\text{sell}} - p_{\text{buy}} \] where \(p_{\text{buy}}\) and \(p_{\text{sell}}\) are the buying and selling prices respectively. Your task is to answer each query efficiently.

inputFormat

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

1. An integer n representing the number of days.
2. A line with n space-separated integers representing the stock prices.
3. An integer q representing the number of queries.
4. q lines, each containing two space-separated integers i and j (with 0 ≤ i ≤ j < n) indicating the start and end indices of the subarray.

outputFormat

Print a single line to standard output (stdout) containing q integers separated by a space. Each integer represents the maximum profit for the corresponding query. If no profit is possible for a query, print 0 for that query.

6
7 1 5 3 6 4
1
0 5

5