Alice and Bob love to play with numbers, one day they found an array with integers consisting of only and . Alice wants to play a range query game with Bob. Alice will give Bob a range from to . Bob needs to tell her who wins or . For to win, the occurrence of in the given range must be strictly greater than that of .
The first line of the input contains an integer denoting the number Integers in the array and an integer denoting the number of queries.
It is followed by a line having integers, denoting the array.
The following lines will have two integers and .
For each query, if is the winner then output should be , otherwise .
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 to , there are zeros and one, so the winner is zero.
For the second query, from to , there are zeros and ones, so is the winner.
Login to submit
At first find the cumulative sum of the given array. After that for each query find the sum of the g...