Fişierul intrare/ieşire:	hapsan.in, hapsan.out	Sursă	FMI No Stress 2017
Autor	Lucian Bicsi	Adăugată de	Fmi No Stress 7 •fmins7
Timp execuţie pe test	0.5 sec	Limită de memorie	66048 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Hapsân

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).

Date de intrare

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

Date de ieşire

Î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.

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ţă

Exemplu

Explicaţie

Gradul maxim de corectitudine este 7, alegând (în ordine) sushi-urile 1 şi 4

Cum se trimit solutii?