clasament

Deoarece este ultimul baraj, comisia în sfârşit se va putea relaxa privind clasamentul concurenţilor în timp real de la probă. Însă, evident, asta nu îi satisface îndeajuns, aşa că ei mai vor să ştie, după fiecare schimbare de punctaj a unui concurent, de câte ori au mai fost concurenţii ordonaţi în ordinea respectivă de-a lungul concursului până în momentul respectiv.

Date de intrare

Fişierul de intrare clasament.in conţine pe prima linie numerele $N$ şi $M$, reprezentând numărul de concurenţi, respectiv numărul de modificări ale clasamentului. Pe următoarea linie se află $N$ numere, punctajele celor $N$ concurenţi înainte de probă (deoarece departajarea a fost foarte bine făcută, toate punctajele sunt diferite). Pe următoarele $M$ linii se află $M$ perechi de numere $x$ şi $y$ ce descriu în ordine cronologică schimbările de punctaj. A $i$-a pereche reprezintă faptul că scorul participantului $x$ a devenit $y$. Punctajul unui concurent la un moment de timp poate fi mai mic decât la începutul concursului, dar se garantează că nu va fi negativ.

Date de ieșire

În fişierul de ieşire clasament.out se vor afişa $M$ linii, pe fiecare linie fiind răspunsul cerut.

Restricții și precizări

• $1 \leq N \leq 50 \ 000$
• $1 \leq M \leq 200 \ 000$
• $1 \leq x \leq N$
• Atât la începutul concursului, cât şi pe parcursul acestuia, punctajele concurenţilor vor fi numere întregi din intervalul $[0, 1 \ 000 \ 000 \ 000]$
• Clasamentul este descrescător după scor.
• În cazul în care $2$ sau mai multe punctaje sunt egale la un moment de timp, concurenţii sunt departajaţi în funcţie de timpul ultimei modificări de punctaj, astfel încât concurentul care a obţinut punctajul mai devreme este clasat mai sus.
• Pentru $20\%$ din teste $1 \leq N, M \leq 2 \ 000$

Exemplu

clasament.in

3 6
10 12 8
1 13
2 15
3 10
1 17
2 20
1 20

clasament.out

0
1
2
1
3
4

Explicație

Moment $0$: clasament: {$2, 1, 3$}, punctaje: {$10, 12, 8$}
Moment $1$: clasament: {$1, 2, 3$}, punctaje: {$13, 12, 8$}
Moment $2$: clasament: {$2, 1, 3$}, punctaje: {$13, 15, 8$} (la fel ca în momentul $0$)
Moment $3$: clasament: {$2, 1, 3$}, punctaje: {$13, 15, 10$} (la fel ca în momentele $0$ şi $2$)
Moment $4$: clasament: {$1, 2, 3$}, punctaje: {$17, 15, 10$} (la fel ca în momentul $1$)
Moment $5$: clasament: {$2, 1, 3$}, punctaje: {$17, 20, 10$} (la fel ca în momentele $0$, $2$ şi $3$)
Moment $6$: clasament: {$2, 1, 3$}, punctaje: {$20, 20, 10$} (la fel ca în momentele $0$, $2$, $3$ şi $5$)
Întrucât ultimul clasament e identic cu primul, putem spune că barajul a fost cam degeaba.