8. Antény

Nad mestom je kopec a na kopci stojí rad antén. Každá anténa je pripojená ku svojmu vysielaču a ten má priradenú nejakú frekvenciu \(f_i\), na ktorej smie vysielať. Všetky vysielače momentálne patria štátu. V meste pod kopcom bývajú dvaja podnikatelia: Amálka a Branko. Obaja by radi založili vlastné rádio, nemajú ale vysielač.

(Amálka si chce založiť Rádio eKSPres, ktoré bude vysielať zaujímavosti zo sveta algoritmov. Brankovo rádio sa bude volať RadioSiTy a dozviete sa z neho o svete 3D grafiky, to ale pre našu úlohu nie je dôležité.)

Povráva sa, že štát čoskoro uvoľní nejaký súvislý úsek antén na kopci a ponúkne ich na prenájom súkromníkom. Nevie sa, ktorý úsek to bude, ale Amálka a Branko už vopred uzavreli dohodu: prenajmú si také dve antény, aby sa frekvencie, na ktorých budú vysielať, líšili aspoň o \(\delta\).

Úloha

Daný je počet antén \(n\), číslo \(\delta\) a frekvencie \(f_0,\dots,f_{n-1}\) na ktorých jednotlivé antény vysielajú. Potom je dané číslo \(q\) a následne \(q\) otázok. Každá otázka je určená dvomi číslami \(l_i\) a \(h_i\) a má nasledovný tvar: “Keby boli na prenájom antény s číslami od \(l_i\) po \(h_i\) vrátane, koľkými rôznymi spôsobmi si vedia Amálka a Branko prenajať dve z nich?”

Napíšte program, ktorý načíta všetky vyššie popísané údaje a následne čo najefektívnejšie odpovie na všetky zadané otázky.

(Dve možnosti považujeme za rôzne, ak sa líšia neusporiadané dvojice indexov antén, ktoré im zodpovedajú. Nezáleží nám teda na tom, kto dostane ktorú anténu z konkrétnej dvojice.)

Formát vstupu

V prvom riadku sú celé čísla \(n\) a \(\delta\) oddelené medzerou: počet antén a minimálny rozdiel frekvencií. Antény sú očíslované od 0 po \(n-1\) v poradí, v ktorom stoja na kopci. Platí \(1\leq\delta\leq 10^6\).

V druhom riadku sú celé čísla \(f_0,\dots,f_{n-1}\): frekvencie pre jednotlivé antény. Platí \(\forall i: 1\leq f_i\leq 10^6\).

V treťom riadku je celé číslo \(q\): počet otázok.

Zvyšok vstupu tvorí \(q\) riadkov, každý z nich obsahuje dve medzerou oddelené celé čísla \(l_i\) a \(h_i\) popisujúce jednu otázku. Pre každú otázku platí \(0\leq l_i < h_i\leq n-1\).

Formát výstupu

Na výstup vypíšte \(q\) riadkov s odpoveďami na otázky, v poradí, v ktorom sú tieto zadané na vstupe.

Hodnotenie

Pre jednotlivé sady vstupov platia nasledovné dodatočné obmedzenia:

Príklad

Input:

5 10
45 60 40 50 45
3
0 2
2 4
0 4

Output:

2
1
5

V prvej otázke vyhovujú dvojice antén \([0, 1]\) a \([1, 2]\) s frekvenciami \([45, 60]\) a \([60, 40]\). V druhej otázke vyhovuje iba dvojica \([2, 3]\) s frekvenciami \([40, 50]\). V tretej otázke vyhovujú dvojice \([0, 1]\), \([1, 2]\), \([1, 3]\), \([1, 4]\) a \([2, 3]\).