Problem 693: Robotul gospodar

Lensu are o grădină foarte mare și iși dorește să ude toate cele $N$ plante puse în linie lângă fântâna lui. Pentru a nu se ofili până seara, fiecare plantă $i \ (i ∈ {1, 2, \dots, N})$ trebuie să primească o cantitate de cel puțin $c_i$ pictături de apă. Acesta nu vrea să iși piardă timpul, așa că roagă echipa de robotică să îl ajute să construiască un robot care să îi facă toata treaba.
Deși au lucrat foarte mult la robot, algoritmul acestuia este foarte ciudat. Din locul în care se află, robotul nostru va uda cu o picătură în fiecare secundă a staționării, toate plantele din intervalul delimitat de cea mai apropiată plantă din stânga cu cantitatea necesară strict mai mică decât cantitatea necesară plantei curente și de cea mai apropiată plantă din dreapta cu cantitatea necesară strict mai mare decât cantitatea necesară plantei curente. Dacă nu există o plantă din stânga cu propietatea de mai sus atunci robotul va uda până la planta $1$ , iar dacă nu există o plantă din dreapta cu propietatea de mai sus atunci robotul va uda până la planta $N$ .

Dimineața, Lensu îi va da robotului $K$ date de tipul:
$X_i$ - locul staționării robotului
$T_i$ - cât timp (în secunde) va staționa acolo

Cerința

Lensu, pasionat de algoritmică presimte că robotul nu este atât de eficient pe cât și-ar fi dorit să fie și vă roagă să îl ajutați să răspundă la următoarea întrebare:
Cunoscând faptul că robotul nu știe când capacitatea plantei este atinsă, astfel continuând să ude planta dacă se află în raza lui de acțiune, care este numărul maxim de plante pe care le-ar putea Lensu salva de la ofilire dacă ar redistribui picăturile irosite, udând alte plante?

Date de intrare

Pe prima linie se afla numărul $N$ , pe a doua linie cele $N$ cantități necesare fiecărei plante, pe a treia linie numărul $K$ , reprezentând numărul de date, iar pe următoarele $K$ linii câte două numere $X_i$ și $T_i$ , cu semnificația din enunț. Numerele aflate pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Pe prima linie se va afla un singur număr, răspunsul la întrebare.

Restricții și precizări

În timpul trecerii de la un loc la altul robotul nu udă nicio plantă
$N \leq 300 \ 000$
$K \leq 150 \ 000$
$c_i \leq 1 \ 000 \ 000, \ (i ∈ {1, 2, ..., N})$
$T_i \leq 1 \ 000 \ 000, \ (i ∈ {1, 2, ..., K})$
$1 \leq X_i \leq N, \ (i ∈ {1, 2, ..., K})$
Pentru $20$ de puncte, $1 \leq N \leq 200$

Observatie

Datorita faptului ca inputul este foarte mare pentru citire se folosesc instructiunile urmatoare la inceputul codului:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Exemplul

stdin

10
3 2 5 1 8 0 4 10 5 3              
4
4 3
7 1
5 2
1 3

stdout

Explicație

Robotul va executa prima comandă și va uda plantele de la poziția $1$ la poziția $5$ , timp de $3$ secunde (cea mai apropiată plantă din stânga cu capacitatea mai mică decât capacitatea plantei $4$ nu există, așa că acesta va începe să ude de la prima plantă, iar cea mai apropiată plantă din dreapta cu capacitatea mai mare decât capacitatea plantei $4$ este planta cu numărul $5$ , având capacitatea $8$ ).
Robotul va executa comanda a doua și analog, după algoritmul prezentat, va uda plantele de la poziția $6$ la poziția $8$ , timp de o secundă.
Robotul va executa comanda a treia și va uda plantele de la poziția $4$ la poziția $8$ , timp de $2$ secunde.
Robotul va executa ultima comandă și va uda plantele de la poziția $1$ la poziția $3$ , timp de $3$ secunde.
La sfârșitul operațiilor fiecare plantă va fi udată timp de:
$6 \ 6 \ 6 \ 5 \ 5 \ 3 \ 3 \ 3 \ 0 \ 0$ secunde.
Se observă că se irosesc $15$ picături pe care le putem redistribui astfel încat să salvam maxim $4$ plante.

Robotul gospodar