== include(page="template/taskheader" task_id="hapsan") ==

h3. _Pentru o masă corectă_

h3. _Pentru o masă corectă._

Fără îndoială, un restaurant care conţine o ofertă de _"All You Can Eat"_ este un restaurant care trebuie vizitat. Cât mai des. De aceeaşi părere este şi personajul din această întamplare, pe care îl vom identifica ipotetic de acum ca **dr. Hapsân**. Mare împătimit al sushi-ului şi, deopotrivă, a mâncării oferite în cantităţi industriale la preţ fix, Hapsân se hotărăşte din nou să facă o vizită restaurantului japonez de peste drum, în speranţa că vă reuşi încă o data să provoace pagube financiare prin oferta acestora, în pofida investiţiei materiale de $50 RON$.

* pe prima linie un număr natural $N$, reprezentând numărul de porţii de sushi care se servesc astăzi la restaurantul de peste drum
* pe a doua linie, $N$ numere naturale $S[1...N]$ separate prin câte un spaţiu, reprezentând gradele de savoare a celor $N$ porţii, **în ordinea în care vor fi servite**
* pe a treia linie, un număr natural $M$, reprezentând numărul de ingrediente diferite de pe parcursul zilei

* pe următoarele $M$ linii, două numere $A[i], B[i]$, separate printr-un spaţiu, cu semnificaţia: _ingredientul $i$ a fost folosit pentru sushi-urile cu numerele de ordine de la $A[i]$ la $B[i]$ **inclusiv**

* pe următoarele $M$ linii, două numere $A[i], B[i]$, separate printr-un spaţiu, cu semnificaţia: _ingredientul $i$ a fost folosit pentru sushi-urile cu numerele de ordine de la $A[i]$ la $B[i]$ **inclusiv**_

h2. Date de ieşire

* $1 ≤ S[i] ≤ 200000$
* $1 ≤ A[i] ≤ B[i] ≤ N$
* Se garantează că fiecare sushi va fi alcătuit din cel puţin un ingredient

* Se estimează că în 70% din cazuri, restaurantul doreşte să ofere servicii cât mai de calitate, aşa că **sushi-urile vor fi servite în ordinea crescătoare a gradelor de savoare** (i.e. $S[i - 1] ≤ S[i]$)

* Se estimează că în 50% din cazuri, restaurantul doreşte să ofere servicii cât mai de calitate, aşa că **sushi-urile vor fi servite în ordinea crescătoare a gradelor de savoare** (i.e. $S[i - 1] ≤ S[i]$)
* Orice asemănare cu vreun personaj real este o pură coincidenţă

h2. Exemplu