Limits 1s, 512 MB

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$.

Input

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)$.

Output

For each query, if $0$ is the winner then output should be $0$, otherwise $1$.

Sample

InputOutput
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 $5$ to $10$, there are $5$ zeros and $1$ one, so the winner is zero.

For the second query, from $1$ to $5$, there are $2$ zeros and $3$ ones, so $1$ is the winner.


Submit

Login to submit.

Statistics

73% Solution Ratio
steinumEarliest, Oct '20
Kuddus.6068Fastest, 0.0s
tarek007Lightest, 524 kB
Being_GoromShortest, 307B
Toph uses cookies. By continuing you agree to our Cookie Policy.