URI Online Judge | 2236

Hot Potato

By Maratona de Programação SBC BR Brazil

Timelimit: 2

Hot potato is a popular game among children in school. The game is simple: the child who is with the potato lance the potato for another child. At some point, the professor, who is not looking at what is going on, will say that the game is over. When this happens, the child is with the potato loses.

A variation of the game, played in the canteen queue, is proposed by a teacher. Children are numbered from 1 to N according to their position in the queue, where the child with the number 1 is the first in line. Each will receive a paper with a number, and when you receive potatoes, should pass it on to the child in the position noted in his role. The game ends with the victorious teacher potatoes arrive at a lower position than or equal to X in line with X set at the start of the game. If this ever happens, the game never ends, but the kids come out victorious: the next day all get a discount in the cafeteria.

The teacher starts the game playing potato for any child in line. As your sight is not very good, it can only guarantee that will play the potato for any child in a invervalo L . . . R in line with the same probability. He is considering several possible queue intervals to start the game. For this, the teacher would like to find out, for each of these intervals, which the value of X that he should choose for the game to be as fair as possible, ie, the probability that the game ends is as close as possible to the probability that the game does not end.

You should help the teacher to evaluate the proposals. Given the roles of each child in line and several possible ranges, respond, for each interval, the value of X that makes the fairest game possible. If there is a tie, answer the X closer to the front of the line.


The first line of input contains two integers, N and Q (2 ≤ N ≤ 50000, 1 ≤ Q ≤ 10 5 ). The next line contains N whole p 1 , p 2 . . . p N (1 ≤ p i N ), the values of roles received by each of the children. Here then Q lines, each with two integers L and R (1 ≤ L R N ), an interval considered by the teacher.


Print Q lines, each containing, for each interval considered by the teacher, the integer X that the teacher should choose for the game to be as fair as possible.

Input Examples Output Examples

9 4

2 3 4 5 6 7 4 9 5

1 3

3 5

2 8

7 9





3 3

1 3 3

1 1

1 2

2 3