16264번 - Array Study 다국어

Vasya likes to study arrays. Recently his parents presented him with an array a that contains elements equal to 1 and  - 1. Vasya immediately started to study it.

Additionally Vasya likes zeroes. So he decided to consider various subarrays a[l_i, ..., r_i] of array a. For each subarray he tries to find the maximum length of its subarray with the sum equal to 0. If there is no such subarray, he considers the answer to be 0. Vasya has written down q subarray requests [l_i, r_i], and now he wants to find the sum of answers to them.

For example, let us consider sample test.

• subarray [1, 5]: the maximal subarray with sum 0 — [2, 5];
• subarray [1, 3]: the maximal subarray with sum 0 — [2, 3];
• subarray [2, 4]: the maximal subarray with sum 0 — [2, 3];
• subarray [3, 4]: no subarray with sum 0;
• subarray [3, 5]: the maximal subarray with sum 0 — [4, 5].

So the sum of answers for the sample test is 4 + 2 + 2 + 0 + 2 = 10.

Input data contains several test cases. The first line contains the number of test cases t (1 ≤ t ≤ 1000).

Each of t test cases is described in the following way: the first line of the description contains n — the number of elements of the array (1 ≤ n ≤ 10⁵).

The following line contains n integers a_i — elements of the array (a_i =  - 1 or a_i = 1).

The following line contains q — the number of subarrays that Vasya is interested in (1 ≤ q ≤ 10⁵).

Each of the following q lines contains two integers l_i, r_i — left and right border of the i-th subarray (1 ≤ l_i ≤ r_i ≤ n)

It is guaranteed that the sum of n in all test cases of one input data doesn't exceed 10⁵, the sum of q in all test cases of one input data doesn't exceed 10⁵.

For each test output one integer — the sum of answers for the given q subarrays.