Pe o portiune de drum se aplica ultimul semn de inceput de zona intalnit. Formal, intre kilometrul $i$ si $i + 1$ viteza maxima e $S[~j~]$, astfel incat $j$ e maxim si $j <= i$ si $S[~j~]$ e cifra. Se garanteaza ca tot timpul va exista un astfel de $j$.

Georgel isi pune $Q$ intrebari de forma "Care este numarul minim de perechi corespondente de semne ce trebuie eliminate astfel incat limita de viteza intre kilometrii $a$ si $b$ sa fie constanta?" si voi trebuie sa il ajutati sa raspunda la ele.

Se dau $Q$ intrebari de forma "Care este numarul minim de perechi corespondente de semne ce trebuie eliminate astfel incat limita de viteza intre kilometrii $a$ si $b$ sa fie constanta?" si voi trebuie sa raspundeti la ele.

h2. Date de intrare