Permutacja [B]

Limit pamięci: 32 MB

Dany jest ciąg liczb naturalnych (dodatnich) , , ..., . Chcielibyśmy ustawić liczby od do w ciąg w takiej kolejności, żeby -ta liczba w ciągu była nie większa niż (dla każdego ). Innymi słowy, szukamy permutacji liczb od do , która spełnia warunek dla każdego . Jest jeszcze jeden problem; otóż ciąg może zmieniać się w czasie...

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę elementów ciągu . Drugi wiersz zawiera ciąg liczb naturalnych (), pooddzielanych pojedynczymi odstępami. Trzeci wiersz zawiera jedną liczbę całkowitą (), oznaczającą liczbę modyfikacji, jakim ma zostać poddany ciąg . Następne wierszy zawiera opisy kolejnych modyfikacji ciągu; każdy z nich składa się z dwóch liczb całkowitych oraz ( dla ), oddzielonych pojedynczym odstępem i oznaczających, że -ty wyraz ciągu uzyskuje nową wartość . Uwaga: zmiany wartości w ciągu następują kolejno, czyli -ta zmiana wykonywana jest w ciągu, który uległ już modyfikacjom od pierwszej do -szej.

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy. Każdy z nich powinien zawierać jedno słowo TAK lub NIE. Słowo znajdujące się w pierwszym wierszu powinno oznaczać, czy istnieje jakaś permutacja spełniająca dla każdego nierówność dla początkowej postaci ciągu , natomiast słowa z wierszy od drugiego do -szego - czy istnieją jakieś (potencjalnie różne) permutacje spełniające podane nierówności dla ciągów powstałych po kolejnych modyfikacjach.

Przykład

Dla danych wejściowych:

5
3 4 3 2 5
2
5 4
1 5

poprawną odpowiedzią jest:

TAK
NIE
TAK

Wyjaśnienie do przykładu. Dla początkowej postaci ciągu wymagane nierówności spełnia m.in. permutacja . Po pierwszej modyfikacji ciąg ma postać - dla takiego ciągu szukana permutacja nie istnieje. Po drugiej modyfikacji ciąg ma postać . Przykładem permutacji spełniającej podane nierówności dla tego ciągu jest .

Autor zadania: Jakub Radoszewski.