Farmer John 認為自己在演算法設計上取得重大突破：他聲稱找到了 3SUM 問題的近線性時間演算法。該問題以尚無已知演算法能顯著優於平方時間而著名。一種表述是：給定整數陣列 $s_1,\dots,s_m$，統計互不相同索引 $i,j,k$ 的無序三元組數，使 $s_i+s_j+s_k=0$。

Bessie 為檢驗此說法，給出含 $N$ 個整數的陣列 $A$（$1\leq N\leq5000$）和 $Q$ 個查詢（$1\leq Q\leq10^5$），各有兩個索引 $1\leq a_i\leq b_i\leq N$。FJ 必須對每個子陣列 $A[a_i\dots b_i]$ 解 3SUM。

不幸他剛發現演算法有漏洞。他相信能修復，但在此期間請你幫他通過 Bessie 的測試！

輸入格式

第一行空格分隔的整數 $N,Q$。第二行空格分隔的陣列元素 $A_1,\dots,A_N$。隨後 $Q$ 行各為空格分隔的整數 $a_i,b_i$，表示查詢。

保證每個 $A_i$ 滿足 $-10^6\leq A_i\leq10^6$。

輸出格式

輸出 $Q$ 行，第 $i$ 行一個整數，為第 $i$ 個查詢的答案。請使用 64 位元整數避免溢位。

範例

輸入格式 1

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

輸出格式 1

2
1
4

說明

第一個查詢的三元組為 $(A_1,A_2,A_5)$ 和 $(A_2,A_3,A_4)$。

子任務

• 測試點 2–4：$N\le500$。
• 測試點 5–7：$N\le2000$。
• 測試點 8–15 無額外限制。

題目作者：Dhruv Rohatgi