Maximum Sales Query

You are given an array representing daily sales amounts for n days and a series of queries. Each query consists of two integers l and r (1-indexed) which represent the start and end day, respectively. Your task is to determine the maximum sales amount in the given range for each query.

Note: The array indexing is 1-based. For each query, find the maximum value in the subarray from sales[l] to sales[r].

The problem can be mathematically formulated as follows:

Given an array \(S = [s_1, s_2, \ldots, s_n]\) and a query \((l, r)\), find the value \(\max\{s_l, s_{l+1}, \ldots, s_r\}\).

inputFormat

The input is given from stdin and follows this format:

• The first line contains an integer n, denoting the number of days.
• The second line contains n space-separated integers representing the sales amounts 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 indicating the start and end day (1-indexed) of a query.

outputFormat

For each query, output the maximum sale amount in the range on a new line to stdout.## sample

5
3 8 5 9 7
2
1 3
2 5

8
9