Maximum Electricity Consumption Query

You are given n houses, each with a certain electricity consumption. The consumption values of the houses are provided in an array. You are then given q queries. Each query consists of two integers l and r (1-indexed), representing a segment of consecutive houses. Your task is to determine the maximum electricity consumption in the segment from the l^th house to the r^th house.

Mathematically, for a consumption array \(C = [C_1, C_2, \dots, C_n]\), and for a query \((l,r)\), you must compute:

[ \max_{l \leq i \leq r} C_i ]

The input is read from standard input (stdin) and the output should be written to standard output (stdout). Each query's answer should be printed on a separate line.

inputFormat

The input begins with an integer n representing the number of houses.

The second line contains n space-separated integers, where each integer represents the electricity consumption of a house.

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, which define a query asking for the maximum consumption in the segment from house l to house r (inclusive).

outputFormat

For each query, output a single line containing the maximum electricity consumption in the given segment.

## sample

5
10 20 12 25 18
3
1 3
2 5
1 5

20
25
25

</p>