Description
There are K treasures hidden deep under the river, and you accidently got a map for these secret treasures.
The map doesn't told you where these treasures were exactly, but it does give you some hint:
We can think of the river as a 1D structure and divided it into N chunks.
The i-th chunk is assigned to a lucky number Ai.
Then, the map gives you some intervals [L, R].
Each interval indicate a secret treasure, and it is hidden in the luckiest chunk in that interval.
The luckiest chunk is defined as following, for an interval [L, R] :
- If L == R, the luckiest chunk is that single chunk L.
- If L < R, find the middle chunk M = (L+R) / 2, then divide the interval into two segment [L, M-1], [M+1, R], and calculate the sum of each segment. The luckest chunk is at the segment with the larger sum.
- If two segments have the same sum, then the luckest chunk is at the segment [M+1, R].
- If a segment contains no numbers (L > M-1 or M+1 > R), then the sum of that segment is 0.
Take the sample input output as an example:
There are three intervals to search for:
For the first interval, L = 1, R = 5, hence M = (1+5)/2 = 3.
Then divide the interval into two segments and calculate their sum:
- L = 1, R = 2, sum = 14
- L = 4, R = 5, sum = 5
Since the segment 1 has the largest sum 14, the luckest chunck is in that segment and we continue search in that segment.
Now, L = 1, R = 2, hence M = (1+2)/2 = 1.
Then divide the interval into two segments and calculate their sum:
- L = 1, R = 0, sum = 0
- L = 2, R = 2, sum = 10
Since the segment 2 has the largest sum 10, the luckest chunck is in that segment and we continue search in that segment.
Now, L = 2, R = 2, since L == R, the luckiest chunk is chunk 2, and the lucky number of that chunk is 10.
--------------------------------------------------------------------------------
For the second interval, L = 4, R = 7, hence M = (4+7)/2 = 5.
Then divide the interval into two segments and calculate their sum:
- L = 4, R = 4, sum = 3
- L = 6, R = 7, sum = 17
Since the segment 2 has the largest sum 17, the luckest chunck is in that segment and we continue search in that segment.
Now, L = 6, R = 7, hence M = (6+7)/2 = 6.
Then divide the interval into two segments and calculate their sum:
- L = 6, R = 5, sum = 0
- L = 7, R = 7, sum = 8
Since the segment 2 has the largest sum 8, the luckest chunck is in that segment and we continue search in that segment.
Now, L = 7, R = 7, since L == R, the luckiest chunk is chunk 7, and the lucky number of that chunk is 8.
--------------------------------------------------------------------------------
For the third interval, L = 6, R = 6, since L == R, the luckiest chunk is chunk 6, and the lucky number of that chunk is 9.
Input
The first line contains two integers N, K, represent the number of the chunks and the number of the treasures.
Next, there would be N lines, each line contains a integers Ai, represents the lucky number of chunk i.
Next, there would be K lines, each line contains two integers Li, Ri, represent the interval i.
For testcase 1~5:
1 ≤ N, K ≤ 1000
For testcase 6:
1 ≤ N, K ≤ 200000
0 ≤ Ai ≤ 10000
Output
Output K lines, each line contains an integer representing the lucky number of luckiest chunk of the i-th interval.
Note that you NEED to print '\n' at the end of the output.