Fişierul intrare/ieşire:	suma6.in, suma6.out	Sursă	Concursul Naţional de Informatică Urmaşii lui Moisil 2017
Autor	Cristian Vintur	Adăugată de	Andrici Cezar •andrici_cezar
Timp execuţie pe test	2.5 sec	Limită de memorie	128000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Suma6

Se dau două numere naturale N şi S şi un şir de N numere naturale a₁, a₂ ... a_N.

Cerinţă

Să se răspundă la Q query-uri de tipul (L,R), pentru fiecare query precizând numărul de perechi (i,j), L ≤ i < j ≤ R cu proprietatea a_i + a_j = S.

Date de intrare

Fişierul de intrare suma6.in conţine pe prima linie numerele naturale N şi S. Pe a 2-a linie se află valorile a₁, a₂ ... a_N separate prin exact un spaţiu. Linia a 3-a conţine Q, numărul de query-uri iar pe fiecare dintre următoarele Q linii, se află două numere L R separate printr-un spaţiu, corespunzătoare unui query.

Date de ieşire

Fişierul de ieşire suma.out va conţine Q linii, pe linia i va fi răspunsul pentru al i-lea query.

Restricţii

• 2 ≤ N ≤ 100.000
• 1 ≤ Q ≤ 200.000
• 0 ≤ a_i ≤ 1.000.000, 1 ≤ i ≤ N
• 1 ≤ L ≤ R ≤ N
• 0 ≤ S ≤ 1.000.000

Exemplu

Explicaţie

De exemplu, pentru ultimul query 1 6, cele 3 perechi sunt: a₁ + a₄ = 10; a₂ + a₅ = 10; a₄ + a₆ = 10.

Cum se trimit solutii?