Sequence and Queries 0

Time limit2.5sMemory limit512 MB

Summary

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.

Level: Hard9 of 10
Topics: Segment tree, Prefix sum, Divide and conquer, Dynamic programming
Solved: No attempts yet

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.

Examples2

Example 1

Input

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

Expected output

Example 2

Input

10
1 -1 1 -1 1 -1 1 -1 1 -1
5
1 10
2 9
3 4
5 5
4 10

Expected output