P7252 [JSOI2011] Lollipop

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.

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 $m$ lines, each containing one integer, representing the overall flavor for each query. If the overall flavor is mixed flavor, output $0$.

### 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