Farmer John risolve 3SUM#9603
Farmer John è convinto di aver fatto una scoperta rivoluzionaria nel campo della progettazione di algoritmi: afferma di aver sviluppato un algoritmo quasi lineare per il noto problema 3SUM, che si ritiene comunemente richieda almeno un tempo quadratico. Una delle formulazioni del problema 3SUM è la seguente: è dato un array di numeri interi s_1, \ldots, s_m. È richiesto contare il numero di terne non ordinate di indici distinti i, j, k per cui vale la condizione s_i + s_j + s_k = 0.
Per verificare l'algoritmo di Farmer John, Bessie ha preparato un array di numeri interi. Effettuerà query, ciascuna delle quali specifica una coppia di indici x_i, y_i (1 \le x_i \le y_i \le n). Per ogni query, Farmer John deve risolvere il problema 3SUM sul sottoarray A[x_i \ldots y_i].
Farmer John vi chiede di aiutarlo a superare la verifica di Bessie.
La prima riga contiene due numeri interi n~(1 \le n \le 5000) e q~(1 \le q \le 10^5).
La seconda riga contiene gli elementi dell'array a_1, \ldots, a_n. Ciascuna delle successive righe contiene due numeri interi x_i e y_i, che specificano una query.
Si garantisce che per ogni elemento a_i dell'array valga la condizione -10^6 \le a_i \le 10^6.
Stampate righe. La -esima riga deve contenere un singolo numero intero — la risposta alla -esima query.
Per la prima query, le terne di indici adatte sono (A_1, A_2, A_5) e (A_2, A_3, A_4).
Esempio 1