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.


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.


For each line of query, you are to output the maximum number of mushrooms collected on a single line.


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



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

Time Limit: 1 Seconds
Memory Limit: 256MB
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 34
2 66
3 0