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 NN integers consisting of only 00 and 11. Alice wants to play a range query game with Bob. Alice will give Bob a range from LL to RR. Bob needs to tell her who wins 00 or 11. For 00 to win, the occurrence of 00 in the given range must be strictly greater than that of 11.

Input

The first line of the input contains an integer N(1N105)N \hspace{.1cm} (1 \leq N \leq 10^5) denoting the number Integers in the array and an integer Q(1Q105)Q \hspace{.1cm} (1 \leq Q \leq 10^5) denoting the number of queries.

It is followed by a line having NN integers, Ai(0Ai1)A_i \hspace{.1cm} (0 \leq A_i \leq 1) denoting the array.

The following QQ lines will have two integers LL and R(1LRN)R \hspace{.1cm} (1 \leq L \leq R \leq N).

Output

For each query, if 00 is the winner then output should be 00, otherwise 11.

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 55 to 1010, there are 55 zeros and 11 one, so the winner is zero.

For the second query, from 11 to 55, there are 22 zeros and 33 ones, so 11 is the winner.


    Discussion

    Statistics


    75% Solution Ratio

    steinumEarliest, Oct '20

    prodip_bsmrstuFastest, 0.0s

    tarek007Lightest, 524 kB

    Being_GoromShortest, 307B

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

    Toph uses cookies. By continuing you agree to our Cookie Policy.