Fişierul intrare/ieşire:orar.in, orar.outSursăPregatire Clasa a 7-a
AutorTeodor PlopAdăugată deteodor94Teodor Plop teodor94
Timp execuţie pe test0.65 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Orar

Datorita apropierii Olimpiadei de Informatica, Gigel trebuie sa lucreze din greu, atat pentru a fi sigur de succesul sau, cat si pentru a isi impresiona parintii.

Acesta isi face un orar de lucru in care, in curs de N zile, el lucreaza in ziua i, un interval egal cu a[i] unitati de timp. La finalul celor N zile insa, parintii ii pun acestuia Q intrebari de tipul:

  • Cat timp ai "pierdut" incepand cu ziua x, pana in ziua y, lucrand la informatica, inclusiv x si y?

Fiind siret, acesta se gandeste parintii vor fi foarte multumiti de el, daca suma tuturor raspunsurilor ce corespund acestor intrebari va fi cat mai mare. Asa ca se gandeste sa modifice timpii sai de lucru din fiecare zi prin urmatoarea operatie:

  • Interschimba numarul unitatilor de timp lucrate in ziua i cu cele din ziua j.

Mai precis, se doreste o rearanjare a sirului initial, astfel incat suma raspunsurilor date de Gigel sa fie maxima.

Curios daca planul lui malefic merge intocmai, acesta va intreaba care este suma maxima a tuturor raspunsurilor la intrebarile parintilor, dupa efectuarea operatiilor prezentate mai sus?

Date de intrare

Fişierul de intrare orar.in contine pe prima linie numarul natural N, iar pe urmatoarea linie N numere naturale din sirul a[i]. Pe linia a treia se va afla numarul natural Q, iar pe urmatoarele Q linii se vor afla cate doua numere naturale x si y.

Date de ieşire

În fişierul de ieşire orar.out se va gasi un singur numar natural, reprezentand suma maxima ce poate fi obtinuta prin adunarea raspunsurilor, dupa efectuarea operatiilor.

Restricţii

  • 1 ≤ N, Q ≤ 200.000
  • 1 ≤ a[i] ≤ 200.000
  • 1 ≤ x ≤ y ≤ N

Exemplu

orar.inorar.outExplicatie
6
5 10 9 8 7 8
3
1 6
4 5
4 4
76
Suma maxima se poate obtine prin urmatoarea aranjare a sirului initial: 5 7 8 10 9 8,
si anume 5 + 7 + 8 + 10 + 9 + 8 + 10 + 9 + 10 = 76.
Trebuie sa te autentifici pentru a trimite solutii. Click aici