Zadanie

Július Cézar

Počet bodov: 60

Július Cézar na svojich vojenských výpravách rád staval palisády. Typicky by mali mať všetky kmene tvoriace palisádu rovnakú výšku, pri dobýjaní jednej nemenovanej Gálskej dediny chcel však skúsiť inú stratégiu - mať rôzne výšky kmeňov, a usporiadať ich od najnižšej po najvyššiu. Aby to bolo estetické, \(i\)-ty kmeň by pritom mal byť aspoň \(i\) vymysľometrov vysoký.

Problém nastal v tom, že kmene sa opotrebúvajú, a tak ich raz za čas bolo treba vymeniť za iné…

Úloha

Máme \(n\) čísel - výšky kmeňov vo vymysľometroch.

Chceme vedieť, či po zoradení od najmenšieho po najväčšie platí, že \(i\)-ty najnižší kmeň má aspoň \(i\) metrov.

Navyše budeme musieť \(q\) krát vymeniť nejaký kmeň za iný, a túto otázku si budeme klásť zakaždým. Tieto zmeny pretrvávajú (zahodené kmene nevraciame).

Vstup a Výstup

V prvom riadku je číslo \(n\) - počet kmeňov v palisáde.

V druhom riadku je \(n\) oddelených celých čísel \(1 \leq v_i \leq n\) - výšky kmeňov.

V treťom riadku je číslo \(q\) - počet výmen, ktoré spravíme.

V každom z nasledujúcich \(q\) riadkov sú dve čísla \(1 \leq k,v \leq n\) označujúce, že \(k\)-ty kmeň (podľa poradia na vstupe) vymeníme za kmeň s výškou \(v\).

Vypíšte \(q+1\) riadkov, v každom ANO alebo NIE podľa toho, či sa dajú kmene zoradiť tak, aby \(i\)-ty z nich mal aspoň \(i\) vymysľometrov; v prvom riadku pre začiatočnú palisádu, v každom ďalšiom po aplikovaní patričnej výmeny.

Sú štyri sady vstupov; v každej platí \(1 \leq n, q \leq 200\,000\).

V prvej sade navyše platí \(n-v_i, n-v \leq 10\).

Príklady

Input:

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

Output:

ANO
NIE
ANO
NIE

Začiatočná palisáda je v pohode. Ak však kmeň s výškou \(4\) zmenšíme, štvrý najnižší kmeň bude nižší ako \(4\), čo je zle. Keď potom získame kmeň výšky \(4\) namiesto \(2\), opäť je všetko v poriadku. Vymenením jediného kmeňu výšky \(5\) si to vzápätí pokazíme.