Cho mảng \(S = [s_1, s_2, \dots, s_N]\) có \(N\) phần tử.

Cho \(Q\) truy vấn có dạng \((a_i, b_i)\), trên mảng con \(S[a_i \dots b_i]\), bạn hãy đếm số bộ ba \(i < j < k\) sao cho \(s_i + s_j + s_k = 0\).

Dữ liệu đầu vào

• Dòng đầu tiên lần lượt chứa hai số \(N\) và \(Q\).
• Dòng thứ hai chứa \(N\) số nguyên \(s_1, s_2, \dots, s_n\) \((\forall i: -10^6 \leq s_i \leq 10^6)\).
• \(Q\) dòng cuối cùng, dòng thứ \(i\) chứa hai số \(a_i, b_i\) \((1 \leq a_i \leq b_i \leq N)\)

Định dạng đầu ra

• In ra \(Q\) dòng, dòng thứ \(i\) chứa một số nguyên 64-bit là đáp án cho truy vấn thứ \(i\).

Điểm số

• Test 1 là test ví dụ
• Test 2-4 thỏa mãn \(N \leq 500\)
• Test 5-7 thỏa mãn \(N \leq 2000\)
• Test 8-15 không có điều kiện nào khác.

Ví dụ

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

2
1
4