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 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.


Submitting to 'collectmushrooms2'


You're not logged in! Click here to login


Submitting to 'collectmushrooms2'


You're not logged in! Click here to login


Submitting .cpp to 'collectmushrooms2'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 62
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 34
2 66
3 0