3SUM trên đoạn

Cho mảng $A$ gồm $N$ phần tử. Trả lời $Q$ truy vấn: với đoạn $[a,b]$, đếm số bộ ba $(i,j,k)$ với $a\le i<j<k\le b$ sao cho $A[i]+A[j]+A[k]=0$.

Dữ liệu vào

• Dòng đầu: $N$ và $Q$.
• Dòng thứ hai: $N$ số nguyên.
• $Q$ dòng tiếp: $a_i$, $b_i$.

Dữ liệu ra

• $Q$ dòng, mỗi dòng số bộ ba thỏa mãn.

Ràng buộc

• $1\le N\le 5000$
• $1\le Q\le {10}^5$
• $|A_i|\le {10}^6$

Ví dụ