ZQUERY - Zero Query

题意翻译

长度为$n$的序列,序列中的值为$1$或$-1$ 有$m$个询问,询问在$[L,R]$中**区间和**为$0$的区间的**最大长度**

题目描述

[English](/problems/ZQUERY/en) [Vietnamese](/problems/ZQUERY/vn)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.

输入输出格式

输入格式


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**).

输出格式


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.

输入输出样例

输入样例 #1

6 4
1 1 1 -1 -1 -1
1 3
1 4
1 5
1 6

输出样例 #1

0
2
4
6