Cho dãy số gồm \(N\) phần tử nguyên dương \(a_1,a_2,…,a_N\).

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vẫn có dạng \(l, r\). Tính số lượng bộ ba chỉ số \((i,j,k)\) với \(l ≤ i <j < k ≤ r\) sao cho \(a_i+a_j+a_k=0\).

Input

• Dòng đầu tiên chứa 2 số nguyên dương \(N,Q(N ≤ 2000,Q ≤ 10^5 ). \)

• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,...,a_n |a_i | ≤ 10^6 )\)

• \(Q\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương \(l,r(l ≤ r ≤ N)\).

Kết quả:

• Đối với mỗi truy vấn, in ra trên một dòng số lượng cách chọn 3 phần tử thỏa mãn.

Sample Input

7 3 
2 0 -1 1 -2 3 3 
1 5 
2 4 
1 7

Sample Output

2
1
4

Ràng buộc

• Subtask 1 (40%) : \(N ≤ 500.\)

• Subtask 2 (60%) : \(N ≤ 2000.\)