Description

Byteasar works for the BAJ company, which sells computer games.

The BAJ company cooperates with many courier companies that deliver the games sold by the BAJ company to its customers.

Byteasar is inspecting the cooperation of the BAJ company with the couriers.

He has a log of successive packages with the courier company that made the delivery specified for each package.

He wants to make sure that no courier company had an unfair advantage over the others.

If a given courier company delivered more than half of all packages sent in some period of time, we say that it dominated in that period.

Byteasar wants to find out which courier companies dominated in certain periods of time, if any.

Help Byteasar out!

Write a program that determines a dominating courier company or that there was none.

Given a sequence of integers, for each query on an interval, determine whether there is a number whose occurrences are more than half of the interval length; if so, report it, otherwise report $0$.

Input Format

The first line contains two integers $n$ and $m$, which are the number of packages shipped by the BAJ company and the number of time periods (queries) for which the dominating courier is to be determined, respectively.

The courier companies are numbered from $1$ to (at most) $C$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ separated by single spaces; $a_i$ is the number of the courier company that delivered the $i$-th package (in shipment chronology).

The next $m$ lines each describe one time period. Each line contains two integers $l$ and $r$, separated by a single space. These mean that the courier company dominating in the period between the shipments of the $l$-th and the $r$-th package, inclusive, is to be determined.

Output Format

Print $m$ lines. Each line should contain a single integer: the number of the courier company that dominated in the corresponding time period, or $0$ if there was no such company.

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

1
0
3
0
4

Hint

Translated by ChatGPT 5