SP4310 AE5B2 - Permutacja

You are given a sequence of positive integers a $ _{1} $ , a $ _{2} $ , . . . , a $ _{n} $ . We would like to order the numbers from 1 to n in such a way, that the i-th number is not greater than a $ _{i} $ (for each i). In other words, we are looking for a permutation p of numbers from 1 to n, which satisfies: p $ _{i} $ ≤ a $ _{i} $ for each 1 ≤ i ≤ n. There is one more problem, the sequence ai may change over time. . .

The first line of standard input contains one integer n (1 ≤ n ≤ 200 000), the number of elements of the a $ _{i} $ sequence. In the second line, there is a sequence of n positive integers a $ _{i} $ (1 ≤ a $ _{i} $ ≤ n), separated by single spaces. The third line contains one integer m (0 ≤ m ≤ 500 000), representing the number of modifications made to the ai sequence. The following m lines describe these modifications. Each description consists of two integers j $ _{i} $ and w $ _{i} $ (1 ≤ j $ _{i} $ , w $ _{i} $ ≤ n for 1 ≤ i ≤ m), separated by single spaces and meaning that j $ _{i} $ -th element of the sequence becomes w $ _{i} $ . The operations take place in turns, so the i-th modification is applied to the sequence altered by (i − 1) previous modifications.

Your program should output exactly m + 1 lines to the standard output. Each of those lines should contain one word TAK (meaning YES) or NIE (meaning NO). The word in the first line should tell if there exists a permutation p, which satisfies p $ _{i} $ ≤ a $ _{i} $ for each i (for the original a $ _{i} $ sequence), whereas the words from following lines answer the question whether there exist any (potentially different) permutations that satisfy the given conditions for the ai sequence after each modification.