constant

Constant

* Daca $S[~i~]$ e $')'$, inseamna sfarsitul restrictiei anterioare (care nu are pereche);
* Daca $S[~i~]$ e $'*'$, inseamna ca nu exista niciun semn la kilometrul $i$.

Deci, notitele lui Georgel pot fi reprezentate ca un sir de caractere cum ar fi $"1*9))"$. Fiecare inceput de zona va avea o pereche corespondenta sfarsit de zona (pozitiile $3-4$ si $1-5$ in sir).

Deci, notitele lui Georgel pot fi reprezentate ca un sir de caractere cum ar fi $"1*9))"$. Fiecare inceput de zona va avea o pereche corespondenta sfarsit de zona (pozitiile $2-3$ si $0-4$ in sir). Intre kilometrii $i$ si $i+1$ se aplica restrictia impusa de ultimul semn (cu indicele ≤ $i$) caruia nu i-am intalnit perechea de sfarsit (verificati exemplul pentru clarificare).

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 $S[~j~]$ e cifra. Se garanteaza ca tot timpul va exista un astfel de $j$.
 
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.

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.

h2. Date de intrare

h2. Restricţii

* Pentru toate testele de la evaluare T = 10
* $2 ≤ N, Q ≤ 100000$

* Pentru toate testele de la evaluare $T = 10$
* $1 ≤ N ≤ 100000$
* $1 ≤ Q ≤ 100000$

* $0 &leq; a < b &leq; N$
* $S$ ca incepe cu o cifra si se va termina cu un caracter $')'$
* $S$ nu va contine cifra $0$

* Nu este permisa eliminarea perechii de semne de pe pozitiile $1 - N+1$ din sir

* Nu este permisa eliminarea perechii de semne de pe pozitiile $0 - N$ din sir (fiindca ar exista portiuni din drum fara restrictii)
* Sumele totale ale $N$-urilor si ale $Q$-urilor nu vor depasi $500000$

h2. Exemplu

Limitele de viteza din primul exemplu sunt urmatoarele:

table(explanation). |_. Interval |_. Viteza maxima |

table(explanation). |_. Interval |_. Limita de viteza |

| $0 - 1$ | $1$ |
| $1 - 2$ | $1$ |
| $2 - 3$ | $9$ |

Pentru a face viteza constanta intre kilometrii $1 - 3$, trebuie sa eliminam perechea de semne care restrictioneaza viteza la $9$.

== include(page="template/taskfooter" task_id="constant") ==
 

== include(page="template/taskfooter" task_id="constant") ==