The 9 Axioms of the Universe#11767
Sign in

The 9 Axioms of the Universe

2 seconds
256 megabytes
Hard

In a world where a conflict erupted between you and Evil Chmyaaax, there exist 9 Axioms that can explain everything (literally everything). The fact that there are exactly nine was proven long ago and is taught in schools, but not all Axioms are known, and not everyone can understand them. If one were to uncover them all, it would open the path to controlling the universe (in the most literal sense). Long ago, Chmyaaax...

Let's see what they study in schools there. Here's an example of a test question from 5th grade, can you solve it?

Let's call an array good if there does not exist a subsegment of it such that the sum of its elements equals 0. Formally: \sum_{i=l}^r b_i \neq 0(1 \le l \le r \le |b|).

There is an array of length and queries to it. Each query is described by the numbers . It is necessary to solve the following problem for each query:

If we consider the subarray of array from to , what is the minimum number of elements that need to be changed so that this subarray becomes good?

Input

The first line contains two integers n(1 \le n \le 5\cdot10^5) and q(1 \le q \le 5\cdot10^5) — the length of array , and the number of queries.

The second line contains integers a_i(-10^9 \le a_i \le 10^9) — the elements of the array .

The next lines contain a pair of integers l_i, r_i(1 \le l \le r \le n) — the parameters of the -th query.

Output

Output integers – the answer to each query.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first query of the first sample, we need to solve the problem on the whole array : [1, 1, 0, -1, 2, -3]. There is a subsegment which has sum of zero, that is why we need to do at least one change to the array to make it good. If we make a_3=47 then array will be good.

In the third query of the second sample, we need to solve the problem on subarray [4, -4, 0]. We can do two changes to make it [4, 47, 47] which is a good array. It can be shown that it is a minimal number of operations to make the subarray good.

Scoring

  1. ( points): n,q \le 15;

  2. ( points): n, q \le 5000;

  3. ( points): If [l, r] is a segment with a sum of , then is also a segment with a sum of ;

  4. ( points): No two segments with a sum of intersect, more formally if [l_1, r_1] and [l_2, r_2] are two different segments with sum then r_2 < l_1 or r_1 < l_2;

  5. ( points): n,q \le 2\cdot10^5;

  6. ( points): no additional constraints;