The 9 Axioms of the Universe

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 $b$ 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\ne 0(1\le l\le r\le |b|)$.

There is an array $a$ of length $n$ and $q$ queries to it. Each query is described by the numbers $l,r$. It is necessary to solve the following problem for each query:

If we consider the subarray of array $a$ from $l$ to $r$, 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\cdot 10^5)$ and $q(1\le q\le 5\cdot 10^5)$ — the length of array $a$, and the number of queries.

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

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

Output

Output $q$ integers – the answer to each query.

Examples

Note

In the first query of the first sample, we need to solve the problem on the whole array $a$: $[1,1,0,-1,2,-3]$. There is a subsegment $[3,3]$ 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. ($6$ points): $n,q\le 15$;

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

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

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

5. ($31$ points): $n,q\le 2\cdot 10^5$;

6. ($19$ points): no additional constraints;