Description
NL is another famous gaming streamer on Twitch. He is known for having only one kidney. One of his fan records the time he streams each day, and he would like to implement a fuction which can tell the longest time NL streamed from day A to day B.
In order to help this crazy fan out, you have to design a program which can find on what day NL streamed for the longest time and output how much hour he streamed on that day in any time interval.
Input
The first line contains an integer N, represents the number of the days which the fan recorded.
The second line contains N integers, i-th number Hi represents the number of hours he streamed on day Hi.
The third line contains an integer M, represents the number of the intervals.
Next, there would be M lines, each line contains two integers A B, represents the starting day and the ending day of the interval. (Starting day A and ending day B are included in the interval.)
Input constraints: (You don't have to type the followings into your code, these are here to show you how large the data would be)
1 ≤ N, M ≤ 1000
0 ≤ Hi ≤ 24
1 ≤ A ≤ B ≤ N
Explanation:
Take sample input as an example:
The first line contains an integer 5, meaning there would be 5 days of records.
Next line contains 5 integers, which means Roger streamed for 2 hours on the first day, 3 hours on the second day, 0 hour on the third day, 7 hours on the fourth day, 5 hours on the fifth day.
The third line contains an integer 3, meaning there would be 3 time interval for queries.
Next, there are 3 lines, first line means from day 3 to day 5, second line means from day 1 to day 2, third line means from day 5 to day 5 (which means there is only on day in this time interval, and it is day 5).
Output
Output M lines, each line contain an integer represents the number of hours Roger streamed in that time interval.
There should be a '\n' at the end of each line.
Explanation:
Take sample ouput as an example:
We can get the answer of the first time interval by comparing streaming hours of day 3, day 4 and day 5, which is 0, 7, 5 respectively, and the answer is 7, since it is the longest.
We can get the answer of the second time interval by comparing streaming hours of day 1 and day 2, which is 2, 3 respectively, and the answer is 3, since it is the longest.
We can get the answer of the third time interval by comparing streaming hours of day 5, which is 5, and the answer is 5, since there is only one day to compare.