== include(page="template/taskheader" task_id="hapsan") ==
Poveste şi cerinţă...
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$.
Restaurantul va servi în această zi **$N$ porţii de sushi**, pe sistem de autoservire. Mai exact, porţiile de sushi vor fi servite în ordinea în care sunt create, urmând ca clientul să opteze la fiecare pas dacă doreşte felul curent sau nu. Fiecare fel este special, însă unele porţii conţin ingrediente comune (în funcţie de stocul ingredientelor pe parcursul zilei). Pentru a simplifica ipoteza, vom considera că există **$M$ ingrediente distincte**, numerotate de la $1$ la $M$, ingredientul $i$ intrând în componţa porţiilor $[Ai...Bi]$.
Bineînţeles, în aceste condiţii _unele combinaţii sunt mai proaste decât altele_ (spre exemplu, pot exista sushi-uri care să nu conţină carne!). Doctor în ale culinăriei gourmet, Hapsân îşi doreşte să evite orice incident neplăcut, aşa că şi-a făcut o listă cu aşa-numitele _grade de savoare_ ale celor $N$ feluri de sushi ce urmează a fi servite. Hapsân doreşte să maximizeze în final **coeficientul de corectitudine** a mesei, definit ca fiind suma gradelor de savoare a sushi-urilor mâncate în această zi.
Cu toate acestea, Hapsân doreşte ca masa lui să fie cât mai variată şi, în acest sens, nu va accepta să mănânce două porţii de sushi care au în componenţă acelaşi ingredient. Mai mult, deoarece nu suportă ideea de a-şi "strica gustul", acesta va accepta să mănânce sushi-ul $i$ după sushi-ul $j$ (cu $j < i$), doar dacă gradul de savoare al sushi-ului $i$ este **strict mai mare** decât cel al sushi-ului $j$.
Cum sunt foarte multe feluri la dispoziţie şi foarte puţin timp de decizie, va trebui să îl ajutaţi pe vestitul doctor să aleagă sushi-urile pe care optează să le mănânce **în ordinea dată** şi respectând condiţiile precizate şi să afişaţi **coeficientul maxim de corectitudine a mesei** pe care îl poate obţine (bineînţeles, ca să demonstraţi ineficienţa lui).
h2. Date de intrare
Fişierul de intrare $hapsan.in$ ...
Fişierul de intrare $hapsan.in$ conţine:
* 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**_
h2. Date de ieşire
În fişierul de ieşire $hapsan.out$ ...
În fişierul de ieşire $hapsan.out$ va conţine un singur număr natural, reprezentând **coeficientul maxim de corectitudine** care poate fi obţinut.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 200000$
* $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 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
table(example). |_. hapsan.in |_. hapsan.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
3 5 6 4
2
1 3
3 4
| 7
|
h3. Explicaţie
...
Gradul maxim de corectitudine este $7$, alegând (în ordine) sushi-urile $1$ şi $4$
== include(page="template/taskfooter" task_id="hapsan") ==
