Fast Range Maximum Query

Given an array of integers and several queries, each query asks for the maximum integer in a subarray. Your task is to preprocess the array to answer the queries efficiently.

The first line of input contains an integer n denoting the number of elements in the array. The second line contains n space-separated integers. The third line contains an integer q denoting the number of queries. Each of the next q lines contains two integers l and r (1-indexed) representing the bounds of the query.

For each query, output the maximum value in the subarray from index l to r on a separate line.

inputFormat

The first line contains an integer n, the number of elements in the array. The second line contains n space-separated integers. The third line contains an integer q, the number of queries. Each of the next q lines contains two integers l and r (1-indexed).

outputFormat

For each query, output the maximum value in the subarray from l to r on a new line.## sample

5
1 2 3 4 5
3
1 3
2 5
1 5

3
5
5