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.


    Discussion

    Statistics


    78% Solution Ratio

    steinumEarliest, 1w ago

    prodip_bsmrstuFastest, 0.0s

    tarek007Lightest, 524 kB

    RAKIB_2001Shortest, 484B

    Submit

    Login to submit

    Editorial

    At first find the cumulative sum of the given array. After that for each query find the sum of the...