3SUM Queries in Subarrays

Farmer John claimed to have achieved a breakthrough in algorithm design by developing an almost linear-time solution for the famous 3SUM problem. In one version of the 3SUM problem, you are given an integer array \(s_1, s_2, \dots, s_m\) and must compute the number of unordered triples of distinct indices \(i, j, k\) such that \(s_i + s_j + s_k = 0\).

To test Farmer John's claim, Bessie provides an array \(A\) of \(N\) integers (\(1 \leq N \leq 5000\)). Bessie will then perform \(Q\) queries (\(1 \leq Q \leq 10^5\)). Each query consists of two indices \(a\) and \(b\) (\(1 \leq a \leq b \leq N\)). For each query, you are required to solve the 3SUM problem on the subarray \(A[a \ldots b]\).

Your task is to help Farmer John pass Bessie's tests by correctly computing the number of triples that sum to zero in each queried subarray. Note that if the subarray contains duplicate values, each combination of distinct indices is counted separately.

inputFormat

The first line contains two integers \(N\) and \(Q\) indicating the size of the array and the number of queries, respectively.

The second line contains \(N\) space-separated integers, representing the array \(A\).

Each of the next \(Q\) lines contains two integers \(a\) and \(b\) indicating a query on the subarray \(A[a \ldots b]\) (1-indexed).

outputFormat

For each query, output one line containing a single integer, the number of triples of distinct indices in the subarray whose sum is zero.

sample

5 1
1 -1 0 2 -2
1 5

2