Permutation

You are given a sequence of positive integers $a_1, a_2, \ldots, a_n$. You want to place the numbers $1$ through $n$, each exactly once, into positions $1$ through $n$, so that the number placed at position $i$ never exceeds $a_i$. In other words, decide whether a permutation $p$ of $1, \ldots, n$ exists such that $p_i \le a_i$ for every $1 \le i \le n$.

Write a program that reports, for the initial sequence and after each single edit to the sequence, whether such a permutation can be formed.

The first line contains the length of the sequence $n$ ($1 \le n \le 200{,}000$). The second line contains $a_1, a_2, \ldots, a_n$ separated by spaces. The third line contains the number of edits $m$ ($0 \le m \le 500{,}000$). Each of the next $m$ lines describes one edit as two integers $j_i$ and $w_i$ ($1 \le j_i, w_i \le n$), meaning the $j_i$-th element is changed to $w_i$. Edits are applied cumulatively: the $i$-th edit is made to the sequence that already includes the previous $i-1$ edits.

Print $m+1$ lines. On each line print TAK if a permutation satisfying the condition can be formed, or NIE if it cannot.

The first line is the answer for the initial sequence, and the next $m$ lines are the answers immediately after the $1$st through $m$th edits are applied.

In the sample, the initial sequence admits the permutation $2, 4, 3, 1, 5$. After the first edit the sequence becomes $3, 4, 3, 2, 4$, for which no permutation exists. After the second edit it becomes $5, 4, 3, 2, 4$, for which the permutation $5, 1, 3, 2, 4$ works.