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.