5. Obrovská rekonštrukcia

Ako už viete z tretej úlohy v predošlej sérii¹, starosta Kocúrkova plánuje rekonštrukciu autobusových zástávok.

Na pripomenutie, Kocúrkovo je jedna dlhá ulica pozdĺž ktorej je postavených \(n\) autobusových zastávok. Každá autobusová linka má dve konečné zastávky, medzi ktorými jej autobusy jazdia hore-dolu, pričom stoja aj na každej zastávke po ceste. Keďže Kocúrkovo je Kocúrkovo, môže sa stať, že niektorá linka začína aj končí na rovnakej zastávke (a teda autobus iba stojí na tejto zastávke).

Z politických dôvodov (o ktorých sa môžete dočítať v zadaniach minulej série) starosta chce, aby od začiatku rekonštrukcie čo najdlhšie platilo, že každý deň sa na každej linke rekonštruuje aspoň jedna zastávka.

Starosta vyhlásil verejnú súťaž a dostal veľa ponúk. Teraz potrebuje zistiť, ktorá z nich je najlepšia. Pomôžete mu ohodnotiť jednotlivé ponuky?

Ponuka o každej zastávke hovorí, ktorý deň sa má rekonštruovať. Kvalita ponuky je najmenšie číslo dňa, v ktorý sa na niektorej linke nebude rekonštruovať ani jedna zastávka.

Úloha

Na vstupe dostanete jednu ponuku rekonštrukcie – pre každú zastávku dostanete deň, v ktorý sa podľa tejto ponuky má rekonštruovať. Ďalej dostanete zoznam všetkých liniek aj s ich konečnými zastávkami. Vypočítajte (a vypíšte) kvalitu tejto ponuky. Inými slovami, pre danú postupnosť dní a zoznam liniek vypíšte najmenšie číslo dňa, v ktorý sa na niektorej linke nerekonštruuje žiadna zastávka.

Formát vstupu

V prvom riadku vstupu sú dve medzerou oddelené celé čísla \(n\) a \(m\) (\(1 \leq n,m \leq 1\,000\,000\)) – počet zastávok a počet autobusových liniek.

Zastávky si očíslujme číslami \(1\) až \(n\) od začiatku Kocúrkova po jeho koniec.

V druhom riadku vstupu je \(n\) medzerou oddelených čísel \(d_1, d_2, \dots, d_n\) (\(0 \leq d_i \leq 10^9\)), kde \(d_i\) udáva číslo dňa od začiatku rekonštrukcie, kedy sa bude rekonštruovať zastávka číslo \(i\). Rekonštrukcia začína dňom číslo \(0\).

Nasleduje \(m\) riadkov, v každom z nich sú dve medzerou oddelené čísla \(z_i\) a \(k_i\) – čísla konečných zastávok \(i\)-tej linky. Platí, že \(1 \leq z_i \leq k_i \leq n\).

Formát výstupu

Vypíšte jediné číslo – najmenšie číslo dňa, v ktorý sa na niektorej linke nerekonštruuje žiadna zastávka.

Príklad

Input:

5 3
0 1 0 1 0
1 3
2 5
4 5

Output:

2

V dni číslo \(0\) a \(1\) sa na každej linke niečo rekonštruuje. V deň číslo \(2\) sa však už nerekonštruuje nič, takže dokonca pre každú linku platí, že sa tam nič nerekonštruuje.

Input:

5 4
0 1 2 1 1
1 3
2 3
1 4
3 5

Output:

0

Na linke \(2\) \(3\) sa nič nedeje v deň číslo \(0\).