Problem Description
Peanut owns a mushroom farm and wants to collect some mushrooms. His mushroom farm has N mushrooms in a row, numbered 0 to N-1 from left to right. Each mushroom i has deliciousness Di. He assigns M minions one by one to help him collect some mushrooms. Each minion i will be assigned a range A to B. However, each minion can only carry at most 1 mushroom, since they have small hands.
Each minion collects the mushroom with the highest deliciousness within the range. If there are multiple mushrooms of the same deliciousness, the minion collects the leftmost of the most delicious mushrooms. If the minion cannot collect any mushrooms, print -1. The collected mushroom is removed from the farm. Help peanut find the deliciousness of the mushrooms collected by each minion.
Input
The first line contains the number N and M.
The second line contains N numbers, representing the array D.
M lines will follow. Each line has 2 integers, A and B, representing the minion i query.
Output
For each line of query, you are to output the maximum number of mushrooms collected on a single line.
Limits
For all subtasks: 0 ≤ A ≤ B < N, 0 ≤ Di ≤ 109
Subtask 1 (34%): 1 ≤ N, M ≤ 2000.
Subtask 2 (66%): 1 ≤ N, M ≤ 200000.
Subtask 3 (0%): Sample Testcases.
Sample Input 1
5 5
3 1 4 2 5
0 1
2 4
1 2
2 4
2 3
Sample Output 1
3
5
4
2
-1
Explanation
Farm has initial mushroom values: 3 1 4 2 5
Minion 0 picks mushroom at position 0.
Minion 1 picks mushroom at position 4.
Minion 2 picks mushroom at position 2.
Minion 3 picks mushroom at position 3.
Minion 4 has no mushrooms to pick.