Manna is a mathematics geek. He loves dealing with functions. One day, he was feeling bored and decided to solve this problem. He is provided with a unimodal array A of values and Q pair of indices. He has to find out the maximum value within this range [low, high]. Help Manna solve this trivial task.
Input Format
The first line contains N, the number of elements in array. The next line contains N elements. The third line contains Q, the number of queries to be made. Then Q lines follow, each containing a space separated pair of numbers. The first number is the low index of the query and the second number is the high index of the query.
Output Format
Display the local maxima, M in a single line for each query. Thus, the final output should contains exactly Q lines.
Constraints
1≤N≤106
1≤A[i]≤108
1≤Q≤106
For the 1st query , the elements present in the range [3,4] are 35 and 85. Among this, the biggest number is 85, hence 85 is the output.
Note: The array is considered to be 1-indexed , i.e. the index of the first element of the array is 1 (instead of 0).
