27368번 - Sum Zero 서브태스크다국어

문제

Roxy, the space traveler, is facing a very abstract problem. Since she’s clueless as to how to solve it, you, as her best friend, have no choice but to help her out:

She is given an array $c_1, c_2, \dots , c_N$ consisting of $N$ integers, and $Q$ pairs of endpoints $(L_i , R_i),ドル each representing the subarray $c_{L_i} , c_{L_i+1}, \dots , c_{R_i},ドル where 1ドル ≤ i ≤ N$.

For each such pair $(L_i , R_i),ドル Roxy is asked what is the maximum number of disjoint sum-0 subarrays one can choose from the queried array $c_{L_i} , c_{L_i+1}, \dots , c_{R_i}$. Two subarrays are considered disjoint if they have no entries in common; however, they can still have neighboring endpoints. Note that, there might be entries from the queried array that are not part of any of the chosen subarrays.

입력

The first line of the input contains a single integer $N$.

The second line contains $N$ space-separated integers $c_1, c_2, \dots , c_N$.

The third line contains the number $Q$ of queries.

The next $Q$ lines contain two numbers $L_i$ and $R_i$ each, representing the $i$^th query.

출력

Print $Q$ lines: on the $i$^th line you should print the answer to the $i$^th query.

제한

• 1ドル ≤ N ≤ 400,000円$
• 1ドル ≤ Q ≤ 400,000円$
• $−10^9 ≤ c_i ≤ 10^9$ for all 1ドル ≤ i ≤ N$
• 1ドル ≤ L_i ≤ R_i ≤ N$ for all 1ドル ≤ i ≤ Q$

서브태스크 1 (22점)

• 1ドル ≤ N ≤ 5,000円$
• 1ドル ≤ Q ≤ 5,000円$

서브태스크 2 (39점)

• 1ドル ≤ N ≤ 100,000円$
• 1ドル ≤ Q ≤ 100,000円$

서브태스크 3 (39점)

• No additional constraints.

힌트