Humorous Subsequence Queries

Given a sequence ( a_1, a_2, \dots, a_n ), we define a contiguous subsequence ( a_l, a_{l+1}, \dots, a_r ) to be ( \textbf{humorous} ) if and only if:

1. \( \sum_{i=l}^{r} a_i > 0 \);
2. For all \( l \le x \le y < r \), we have \( \sum_{i=x}^{y} a_i \le 0 \).

You are given ( q ) queries. Each query contains two integers ( l ) and ( r ), and you must count the number of pairs ( (l', r') ) satisfying:

• \( l \le l' \le r' \le r \);
• The contiguous subsequence \( a_{l'}, a_{l'+1}, \dots, a_{r'} \) is humorous.

Note: A subsequence of length 1 is humorous if and only if \( a_i > 0 \). For longer subsequences, every proper contiguous subinterval (i.e. any interval that does not extend to the end of the subsequence) must have a non-positive sum.

inputFormat

The first line contains two integers \( n \) and \( q \) representing the length of the sequence and the number of queries respectively.

The second line contains \( n \) space-separated integers \( a_1, a_2, \dots, a_n \).

Each of the next \( q \) lines contains two integers \( l \) and \( r \) describing a query.

outputFormat

For each query, output a single integer denoting the number of humorous subarrays within the range \( [l, r] \).

sample

3 2
1 -2 3
1 3
2 3

1
1

</p>