Farmer John glaubt an einen Durchbruch: einen fast linearen Algorithmus für 3SUM, bekannt dafür, dass keine wesentlich schnellere als quadratische Lösung bekannt ist. Eine Formulierung: Für ein ganzzahliges Array $s_1,\dots,s_m$ zähle ungeordnete Tripel verschiedener Indizes $i,j,k$ mit $s_i+s_j+s_k=0$.

Bessie testet dies mit einem Array $A$ aus $N$ ganzen Zahlen ($1\leq N\leq5000$) und $Q$ Anfragen ($1\leq Q\leq10^5$), jeweils mit $1\leq a_i\leq b_i\leq N$. 3SUM ist jeweils auf $A[a_i\dots b_i]$ zu lösen.

Leider fand FJ gerade einen Fehler. Er glaubt, ihn beheben zu können, bittet aber inzwischen um Hilfe beim Test von Bessie!

Eingabe

Erste Zeile: ganze Zahlen $N,Q$ durch Leerzeichen getrennt. Zweite: Elemente $A_1,\dots,A_N$ durch Leerzeichen getrennt. Die nächsten $Q$ Zeilen enthalten je die ganzen Zahlen $a_i,b_i$ durch Leerzeichen getrennt für eine Anfrage.

Jedes Element erfüllt $-10^6\leq A_i\leq10^6$.

Ausgabe

$Q$ Zeilen; Zeile $i$ enthält eine ganze Zahl als Antwort auf Anfrage $i$. Verwende 64-Bit-Ganzzahlen gegen Überlauf.

Beispiele

Eingabe 1

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

Ausgabe 1

2
1
4

Hinweis

Die Tripel der ersten Anfrage sind $(A_1,A_2,A_5)$ und $(A_2,A_3,A_4)$.

Teilaufgaben

• Tests 2–4: $N\le500$.
• Tests 5–7: $N\le2000$.
• Tests 8–15: keine weiteren Einschränkungen.

Aufgabenautor: Dhruv Rohatgi