# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Binary Game

By Nasif_44th · 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.

### Statistics

75% Solution Ratio

steinumEarliest, Oct '20

prodip_bsmrstuFastest, 0.0s

tarek007Lightest, 524 kB

Being_GoromShortest, 307B

### Submit 