Background

@【data deleted】: What do you all think? || @【data deleted】: OI life is always full of humor. But maybe studying school subjects is not much better?

Problem Description

Given a sequence $a_1,a_2,\cdots,a_n$ of length $n$, define a contiguous subsequence $a_l,a_{l+1},\cdots,a_r$ to be humorous if and only if:

• $\sum\limits_{i=l}^r a_i>0$;
• For all $l\le x\le y<r$, we have $\sum\limits_{i=x}^y a_i\le 0$.

There are $q$ queries. In each query, you are given two integers $l,r$, and you need to count the number of pairs $(l',r')$ that satisfy:

• $l\le l'\le r'\le r$;
• The contiguous subsequence $a_{l'},a_{l'+1},\cdots a_{r'}$ is humorous.

Input Format

The first line contains two integers $n,q$.

The next line contains $n$ integers, where the $i$-th integer is $a_i$.

The next $q$ lines each contain two integers $l,r$, representing a query.

Output Format

For each query, output one integer per line, which is the answer.

4 3
3 -4 -1 2
1 2
3 4
1 4

1
2
3

7 6
-1 2 -1 -1 -1 2 -1
2 5
4 7
1 7
5 5
1 3
2 4

1
2
4
0
2
1

Hint

For all testdata, it is guaranteed that $1\le n,q\le 2\times 10^5$, $1\le l\le r\le n$, and $|a_i|\le 10^9$.

Subtasks

Translated by ChatGPT 5