ZQUERY - Zero Query


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: 2018-01-06 12:59:39

Woah! Took so much of time trying to fix minor bugs. Finally AC. :)
People trying to build up on QCHEF solution, ensure you're handling the number before the start of the current block as well.

shubham: 2017-11-04 21:45:06

Problem can be reduced to
https://www.codechef.com/problems/QCHEF

shubham: 2017-10-31 04:20:33

Last edit: 2017-11-04 21:40:21
starbot: 2017-10-10 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: 2017-07-31 15:38:24

Really interesting problem. Can be solved without MO :)

rajeev_899: 2017-06-29 07:20:49

what will be the answer for this
6 1
-1 1 1 1 1 -1
1 6

answer must be 2 isn't it?
but the AC solution giving answer 4 and still AC how???

Last edit: 2017-06-29 07:21:40
_________++++__________: 2017-02-01 20:38:43

Great question to understand MO algorithm

titanlord89: 2016-10-17 12:00:40

Someone please have a look at my code. It WAs even though it passes everything I throw at it.
Problem code: 17951896
I'm using MO's algorithm and summing.

Last edit: 2016-10-17 12:01:17
ziadxkabakibi: 2016-08-15 14:48:20

Nice One ! can be solved using mo and binary search :D

singhmanmeet40: 2016-08-13 01:07:55

@What Does The Fox Say?
my code uses mo's with multiset
its getting tle on test case 10
time complexity n *(rootn)*logn
submission id:17493739
i tried changing mo's block size to 4 rootn and 2 root n
but still tle

-- setter --
- STL containers' complexity have high constant factors, use other structures or optimize them.

Last edit: 2016-08-13 18:03:37

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