Kaitlyn is collecting statistics for the latest iteration of the Berkeley Math Tournament. In the last tournament, she had ~N~ students numbered from ~1~ to ~N~ participating. Each student received a score that was a positive integer number of points.
One day, Sylvia, her archnemesis, wanted to collect statistics about how well students did in the tournament. Sylvia has ~Q~ questions. Each question takes the form: Among all students from ~L_i~ to ~R_i~, what was the most frequent score among the given students?
Kaitlyn is a nice person and wants the students to look as good as possible, so if multiple scores are tied for most frequent, she will tell Sylvia the largest mode.
Sylvia is impatient, so please answer her questions as quickly as possible!
~1 \le N, Q \le 10^5~
~1 \le s_i \le N~
~1 \le L_i \le R_i \le N~.
In tests worth 1 mark, ~N, Q \le 10^3~.
In tests worth an additional 2 marks, ~N, Q \le 10^4~.
In tests worth an additional 3 marks, ~N, Q \le 2 \cdot 10^4~.
In tests worth an additional 4 marks, ~N, Q \le 5 \cdot 10^4~.
The first line contains two integers, ~N~ and ~Q~.
The next line contains ~N~ integers, the scores ~s_i~ of the students from ~1~ to ~N~ in order.
The next ~Q~ lines contain two integers each, ~L_i~ and ~R_i~, indicating the set of students Sylvia is asking about.
Output ~Q~ lines. On line ~i~, output the answer to Sylvia's ~i~th question.
5 3 2 1 2 1 1 1 2 1 4 1 5
2 2 1