Sequence and Queries 0

For each query range [i,j] of a ±1 sequence, report the length of the longest contiguous subarray inside it whose sum is 0, or 0 if none exists.

Hard9Segment treePrefix sumDivide and conquerDynamic programmingNo attempts yetTime limit2.5sMemory limit512 MB

Description

Examples2

Problem

You are given a sequence $A_1, A_2, \dots, A_N$ of length $N$ in which every element is $1$ or $-1$ . Write a program that answers the following query.

i j: among the contiguous subsequences contained in $A_i, A_{i+1}, \dots, A_j$ , take those whose elements sum to $0$ and print the length of the longest one. Print $0$ if no contiguous subsequence sums to $0$ .

Input

The first line contains the size of the sequence $N$ ( $1 \le N \le 100\,000$ ).

The second line contains $A_1, A_2, \dots, A_N$ separated by spaces. ( $A_i$ is $1$ or $-1$ )

The third line contains the number of queries $M$ ( $1 \le M \le 100\,000$ ).

Each of the next $M$ lines holds one query, given as two integers $i$ and $j$ ( $1 \le i \le j \le N$ ).

Output

Print the answer to each query on its own line, in the order the queries are given.