배열 공부

Vasya는 배열을 공부하는 것을 좋아한다. 최근 부모님이 1과 -1로만 이루어진 배열 $a$를 선물로 주셨고, Vasya는 곧바로 이 배열을 공부하기 시작했다.

Vasya는 0도 좋아한다. 그래서 배열 $a$의 여러 부분 배열 $a[l_i, \ldots, r_i]$를 살펴보기로 했다. 각 부분 배열마다 합이 0인 부분 배열의 최대 길이를 구한다. 그러한 부분 배열이 없으면 답을 0으로 본다. Vasya는 $q$개의 부분 배열 질의 $[l_i, r_i]$를 적어 두었고, 이제 각 질의의 답을 모두 더한 값을 구하려고 한다.

예를 들어 예제를 보자.

• 부분 배열 $[1, 5]$: 합이 0인 최대 부분 배열은 $[2, 5]$이다.
• 부분 배열 $[1, 3]$: 합이 0인 최대 부분 배열은 $[2, 3]$이다.
• 부분 배열 $[2, 4]$: 합이 0인 최대 부분 배열은 $[2, 3]$이다.
• 부분 배열 $[3, 4]$: 합이 0인 부분 배열이 없다.
• 부분 배열 $[3, 5]$: 합이 0인 최대 부분 배열은 $[4, 5]$이다.

따라서 예제의 답을 모두 더하면 $4 + 2 + 2 + 0 + 2 = 10$이다.

입력은 여러 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 1000$).

각 테스트 케이스는 다음과 같다. 첫째 줄에 배열의 원소 수 $n$이 주어진다 ($1 \le n \le 10^5$).

다음 줄에 $n$개의 정수 $a_i$가 주어진다. $a_i$는 배열의 원소이며 $a_i = -1$ 또는 $a_i = 1$이다.

다음 줄에 Vasya가 궁금해하는 부분 배열의 수 $q$가 주어진다 ($1 \le q \le 10^5$).

이어서 $q$개의 줄에 두 정수 $l_i, r_i$가 주어진다. 각각 $i$번째 부분 배열의 왼쪽과 오른쪽 경계이다 ($1 \le l_i \le r_i \le n$).

한 입력 데이터의 모든 테스트 케이스에서 $n$의 합은 $10^5$을 넘지 않고, $q$의 합도 $10^5$을 넘지 않는다.

각 테스트 케이스마다 주어진 $q$개의 부분 배열에 대한 답의 합을 한 정수로 출력한다.