Boring Opening Ceremony

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka are experienced participants in informatics olympiads. They have been participating since the days when the grass was greener, big integer arithmetic was more popular, and you, dear children, were not yet born. No one can say for sure how many contests they have attended — they lost count after forty-seven.

Before every serious competition that Zenyk and Marichka participate in, there is an opening ceremony. Today’s regional olympiad is no exception.

Today our pair came to the opening ceremony of the olympiad along with everyone else. Here the organizers address the participants and their teachers with a welcoming speech, explain the rules, announce which compilers are available on Algotester and which are not — nothing interesting for such experienced programmers. Therefore, so as not to die of boredom, Zenyk came up with a problem and gave it to Marichka to solve.

You are given an array \(a\) of \(n\) integers. You need to answer \(q\) queries: how many non-empty subarrays with a zero sum exist within the range \([l, r]\).

Before the welcoming part of the opening ceremony even finished, Marichka came up with a solution to the problem.

You, however, need not only to come up with a solution but also to write a program. Go ahead!

Input

The first line contains an integer \(n\) — the size of the array.

The second line contains \(n\) integers \(a_i\) — the elements of the array.

The third line contains an integer \(q\) — the number of queries.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) — the bounds of the segment for which you need to answer the query.

Output

Output \(q\) integers on separate lines — the answers to all queries.

Constraints

\(1 \le n \le 500\),

\(|a_i| \le 10\),

\(1 \le q \le 1000\),

\(1 \le l \le r \le n\).

Problem evaluation consists of the following subtasks:

1 point — example from the statement,

14 points — \(n \le 100\),

10 points — no additional constraints.

You will receive the points for a subtask only if you give the correct answer to all tests in that subtask.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 -2 3 1 -2 1 3 1 5 2 4 3 5	2 0 1

Notes

• The segment \([1, 5]\) contains two subarrays with a zero sum: subarray \([1, 4]\) (\(a_1+a_2+a_3+a_4=-2+3+1+(-2)=0\)) and subarray \([3, 5]\) (\(a_3+a_4+a_5=1+(-2)+1=0\)).

• The segment \([2, 4]\) does not contain any subarrays with a zero sum.

• The segment \([3, 5]\) contains one subarray with a zero sum — itself.