Hot Potato

Time limit2sMemory limit512 MB

Summary

For each query range, find the smallest X maximizing the gap between ending and not ending, given a functional graph walk from a uniform random start.

Level: Hard8 of 10
Topics: Graph, Probability, Math, Binary search
Solved: No attempts yet

Problem

Hot potato is a game children play at school. The rules are simple. The child holding the potato throws it to another child, and at some point the teacher, who is not watching, announces that the game is over. Whoever holds the potato at that moment loses.

A teacher proposed a variation played in the cafeteria line. The children are numbered 1 to $N$ by their position in the line, and child 1 stands at the front. Each child receives a slip of paper with one number on it, and whenever a child receives the potato, that child must pass it to the child at the position written on the slip. The game ends with the teacher winning if the potato lands on a position at most $X$ . The teacher fixes $X$ before the game starts, and $1 \le X \le N$ . If the potato never lands on a position at most $X$ , the game never ends and the children win instead: the next day they all get a discount in the cafeteria.

The teacher starts the game by throwing the potato to one of the children. His aim is poor, so all he can guarantee is that he throws it to one of the children in positions $L$ through $R$ , each with the same probability. The position the potato first lands on counts as a position the potato lands on, so if the first child to receive it has a number at most $X$ , the game ends right there.

The teacher is considering several candidate ranges, and for each one he wants the $X$ that makes the game as fair as possible. Fair here means the difference between the probability that the game ends and the probability that it does not end is as small as possible. Given every child's slip and the candidate ranges, report that $X$ for each range. When several values of $X$ are equally fair, answer with the one closer to the front of the line, that is, the smallest $X$ .

Input

The first line contains two integers $N$ and $Q$ . The second line contains $N$ integers $p_1, p_2, \dots, p_N$ , where $p_i$ is the number on the slip child $i$ received. Each of the next $Q$ lines contains two integers $L$ and $R$ , one range the teacher is considering.

Constraints

$2 \le N \le 50000$
$1 \le Q \le 100000$
$1 \le p_i \le N$
$1 \le L \le R \le N$

Output

Print $Q$ lines. Line $i$ contains the integer $X$ the teacher should choose for the $i$ -th range.

Examples4

Example 1

Input

9 4
2 3 4 5 6 7 4 9 5
1 3
3 5
2 8
7 9

Expected output

Example 2
Input
```
3 3
1 3 3
1 1
1 2
2 3
```
Expected output
```
1
1
2
```
Example 3
Input
```
2 3
2 1
1 1
2 2
1 2
```
Expected output
```
1
1
1
```

Example 4

Input

6 6
1 2 3 4 5 6
1 6
2 5
1 1
6 6
3 6
2 6

Expected output