Alice and Bob love to play with numbers, one day they found an array with $N$
integers consisting of only $0$
and $1$
. Alice wants to play a range query game with Bob. Alice will give Bob a range from $L$
to $R$
. Bob needs to tell her who wins $0$
or $1$
. For $0$
to win, the occurrence of $0$
in the given range must be strictly greater than that of $1$
.
The first line of the input contains an integer $N \hspace{.1cm} (1 \leq N \leq 10^5)$
denoting the number Integers in the array and an integer $Q \hspace{.1cm} (1 \leq Q \leq 10^5)$
denoting the number of queries.
It is followed by a line having $N$
integers, $A_i \hspace{.1cm} (0 \leq A_i \leq 1)$
denoting the array.
The following $Q$
lines will have two integers $L$
and $R \hspace{.1cm} (1 \leq L \leq R \leq N)$
.
For each query, if $0$
is the winner then output should be $0$
, otherwise $1$
.
Input | Output |
---|---|
10 3 0 1 0 1 1 0 0 0 0 0 5 10 1 5 1 10 | 0 1 0 |
For the first query, from For the second query, from |