수열과 쿼리 0

$1$과 $-1$로만 이루어진 길이 $N$의 수열 $A_1, A_2, \dots, A_N$이 주어진다. 아래 쿼리를 처리하는 프로그램을 작성하시오.

• i j: $A_i, A_{i+1}, \dots, A_j$ 안에 들어 있는 연속 부분 수열 중 원소의 합이 $0$인 것을 찾고, 그중 가장 긴 것의 길이를 출력한다. 합이 $0$인 연속 부분 수열이 하나도 없으면 $0$을 출력한다.

첫째 줄에 수열의 크기 $N$ ($1 \le N \le 100\,000$)이 주어진다.

둘째 줄에 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($A_i$는 $1$ 또는 $-1$)

셋째 줄에 쿼리의 개수 $M$ ($1 \le M \le 100\,000$)이 주어진다.

넷째 줄부터 $M$개의 줄에 쿼리가 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $i$, $j$ ($1 \le i \le j \le N$)가 있다.

쿼리마다 답을 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.