SP4310 AE5B2 - Permutacja

给定一个正整数序列 $a_1, a_2, \ldots, a_n$。我们的目标是将数字 $1$ 到 $n$ 排列成一个新的序列 $p$，要求对于每个位置 $i$，都有 $p_i \le a_i$。也就是说，我们希望找到一个排列，使得排列中的每个数字都不大于相应位置上的限制值。 需要注意的是，序列 $a_i$ 在过程中可能会被修改。

第一行包含一个整数 $n$（$1 \le n \le 200\,000$），表示序列 $a$ 的长度。第二行包含 $n$ 个正整数 $a_i$（$1 \le a_i \le n$），它们用空格分隔。第三行一个整数 $m$（$0 \le m \le 500\,000$），表示对序列的修改次数。接下来的 $m$ 行描述这些修改操作。每次修改由两个整数 $j_i$ 和 $w_i$ 组成（$1 \le j_i, w_i \le n$），表示将第 $j_i$ 个元素更新为 $w_i$。这些修改是依次进行的，因此第 $i$ 次修改是在前 $i-1$ 次修改后的序列上进行。

输出包含 $m + 1$ 行，每行一个单词。第一行输出 `TAK` 或 `NIE`，表示对原始序列 $a_i$ 是否存在满足条件的排列。接下来的每行则表示每次修改后的序列是否存在符合条件的排列。`TAK` 代表「存在」，`NIE` 代表「不存在」。

- $1 \le n \le 200\,000$ - $1 \le a_i \le n$ - $0 \le m \le 500\,000$ - $1 \le j_i, w_i \le n$ **本翻译由 AI 自动生成**