ZQUERY  Zero Query
English  Vietnamese 
Given an array having N elements, each element is either 1 or 1.
You have M queries, each query has two numbers L and R, you have to answer the length of the longest subarray in range L to R (inclusive) that its sum is equal to 0.
Input
The first line contains two numbers N and M (1 <= N, M <= 50000)  the number of elements and the number of queries.
The second line contains N numbers  the elements of the array, each element is either 1 or 1.
In the next M lines, each line contains two numbers L and R (1 <= L <= R <= N).
Output
For each query, print the length of the longest subarray that satisfies the query in one line. If there isn't any such subarray, print 0.
Note
Subarray in an array is like substring in a string, i.e. subarray should contain contiguous elements.
Example
Input: 6 4 1 1 1 1 1 1 1 3 1 4 1 5 1 6
Output: 0 2 4 6
hide comments
DOT:
20180106 12:59:39
Woah! Took so much of time trying to fix minor bugs. Finally AC. :)


shubham:
20171104 21:45:06
Problem can be reduced to


shubham:
20171031 04:20:33
Last edit: 20171104 21:40:21 

starbot:
20171010 21:36:26
@What Does The Fox Say? my submission id 20336783 is getting tle...However i think my solutions complexity is O(M*root(N)*Log(N))...could please look into it; 

mahmud2690:
20170731 15:38:24
Really interesting problem. Can be solved without MO :) 

rajeev_899:
20170629 07:20:49
what will be the answer for this


_________++++__________:
20170201 20:38:43
Great question to understand MO algorithm 

titanlord89:
20161017 12:00:40
Someone please have a look at my code. It WAs even though it passes everything I throw at it.


ziadxkabakibi:
20160815 14:48:20
Nice One ! can be solved using mo and binary search :D 

singhmanmeet40:
20160813 01:07:55
@What Does The Fox Say?

Added by:  What Does The Fox Say? 
Date:  20140807 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 