Farmer John はアルゴリズム設計の大きな突破口として、3SUM のほぼ線形時間アルゴリズムを発見したと主張します。この問題は二乗時間を大幅に下回る既知解法がないことで有名です。一つの定式化は、整数配列 $s_1,\dots,s_m$ について $s_i+s_j+s_k=0$ となる相異なる添字 $i,j,k$ の順序を区別しない三つ組を数えるものです。

検証のため Bessie は $N$ 個の整数の配列 $A$（$1\leq N\leq5000$）と $Q$ 個のクエリ（$1\leq Q\leq10^5$）を与えます。各クエリは $1\leq a_i\leq b_i\leq N$ で、部分配列 $A[a_i\dots b_i]$ の 3SUM を解きます。

残念ながら FJ は欠陥を発見しました。修正できると信じていますが、その間テストに合格する手伝いをしてください！

入力

最初の行に空白区切りの $N,Q$。次の行に配列要素 $A_1,\dots,A_N$ を空白区切りで与えます。続く $Q$ 行は空白区切りの整数 $a_i,b_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