collectmushrooms2

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 D_i. 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 ≤ D_i ≤ 10⁹

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.