Farmer John Solves 3SUM

Farmer John is convinced that he has made a groundbreaking discovery in algorithm design: he claims to have developed a nearly linear algorithm for the well-known 3SUM problem, which is widely believed to require at least quadratic time. One formulation of the 3SUM problem is as follows: given an array of integers $s_1,\dots ,s_m$, count the number of unordered triplets with distinct indices $i,j,k$ such that $s_i+s_j+s_k=0$.

To test Farmer John's algorithm, Bessie has prepared an array $A$ of $n$ integers. She will make $q$ queries, each specifying a pair of indices $x_i,y_i(1\le x_i\le y_i\le n)$. For each query, Farmer John must solve the 3SUM problem on the subarray $A[x_i\dots y_i]$.

Farmer John asks for your help to pass Bessie's test.

Input

The first line contains two integers $n(1\le n\le 5000)$ and $q(1\le q\le 10^5)$. The second line contains the elements of the array $a_1,\dots ,a_n$. Each of the following $q$ lines contains two integers $x_i$ and $y_i$, representing a query.

It is guaranteed that for every element of the array $a_i$, the condition $-10^6\le a_i\le 10^6$ holds.

Output

Print $q$ lines. The $i$-th line should contain a single integer — the answer to the $i$-th query.

Examples

For the first query, the possible triplets are: $(a_1,a_2,a_5)$ and $(a_2,a_3,a_4)$.