Eliminare

eliminare

h2. Date de intrare

Pe prima linie a fisierului de intrare $eliminare.in$ sunt scrise doua numere naturale separate printr-un spatiu $n m$, reprezentand numarul de elemente din sirul initial si respectiv numarul de operatii de eliminare. Pe urmatoarele $n$ linii sunt scrise numerele sirului initial, cate unul pe linie. Fiecare dintre ultimele $m$ linii contin doua numere naturale separate printr-un spatiu $i j$ reprezentand indicii intre care se executa o operatie de eliminare. Mai exact, pe linia $1+n+k$ $(1≤k≤m)$ este scris intervalul corespunzator celei de-a $k$-a eliminari $(1≤i≤j≤n-k+1)$.

Pe prima linie a fisierului de intrare $eliminare.in$ sunt scrise doua numere naturale separate printr-un spatiu $n m$, reprezentand numarul de elemente din sirul initial si respectiv numarul de operatii de eliminare. Pe urmatoarele $n$ linii sunt scrise numerele sirului initial, cate unul pe linie. Fiecare dintre ultimele $m$ linii contin doua numere naturale separate printr-un spatiu $i j$ reprezentand indicii intre care se executa o operatie de eliminare. Mai exact, pe linia $1+n+k$ $(1≤k≤m)$ este scris intervalul corespunzator celei de-a  $k$ -a eliminari $(1≤i≤j≤n-k+1)$.

h2. Date de iesire

In fisierul de iesire $eliminare.out$ se vor scrie cele $n-m$ numere ramase, respectand ordinea initiala, cate un numar pe o linie.

...

h2. Restrictii

* $2 ≤ n ≤ 1 000 000$
* $1 ≤ m ≤ min(n-1, 500 000)$
* Termenii sirului sunt numere naturale nenule din mai mici sau egale decat $300 000$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. eliminare.in |_. eliminare.out |

|8 5
 3
 7
 2
 5
 8
 5
 9
 4
 2 5
 6 6
 3 6
 2 5
 1 2
|2
 5
 4

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

== include(page="template/taskfooter" task_id="eliminare") ==

h3. Explicatie
 
...
== include(page="template/taskfooter" task_id="eliminare") ==

1851