Description

Lollipops are also sold in Coffee’s world. Coffee bought $n$ connected lollipops. These $n$ lollipops are wrapped in small plastic bags and arranged in a line, and the plastic bags of two adjacent lollipops are attached to each other. For convenience, we number the lollipops from left to right as $1\cdots n$.

Each lollipop has a flavor. The flavor of the $i$-th lollipop is $c_i$. Two lollipops $i,j$ have the same flavor if and only if $c_i=c_j$. Coffee’s way of judging the overall flavor of $m$ lollipops is somewhat strange. If among these $m$ lollipops, there is a flavor $c_0$ whose count is strictly greater than half of the total, then Coffee thinks these $m$ lollipops are mainly of flavor $c_0$. Coffee knows that if such a $c_0$ exists, it must be unique. If $c_0$ does not exist, Coffee thinks these $m$ lollipops are mixed flavor.

Coffee is not willing to eat the lollipops for now, and is thinking about some interesting questions. Consider a contiguous subsequence $s\cdots t(1\leq s\leq t\leq n)$ of the lollipop sequence, including lollipops $s$ and $t$. What is the overall flavor of these $t-s+1$ lollipops?

Coffee has many such questions, $m$ in total. The $i$-th question asks for the overall flavor of the lollipop subsequence $s_i\cdots t_i$. Please help solve them.

Input Format

The first line contains two integers separated by spaces, representing $n,m$.

The next $n$ lines each contain one integer, representing $c_i$.

The next $m$ lines each contain two integers, representing $s_i,t_i$.

Output Format

Output $m$ lines, each containing one integer, representing the overall flavor for each query. If the overall flavor is mixed flavor, output $0$.

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

1
0
2

Hint

Sample Explanation 1

In the first query, flavor $1$ appears $3$ times, which is more than half of the total, so the overall flavor is $1$.

In the second query, no flavor appears more than half of the total, so it is mixed flavor.

In the third query, flavor $2$ appears $2$ times, which is more than half of the total, so the overall flavor is $2$.

Constraints

For $100\%$ of the testdata, $1\leq n,m,c_i\leq 5\times 10^4$.

Translated by ChatGPT 5