AE5B2 - Permutacja

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

Input

The first line of standard input contains one integer n (1 ≤ n ≤ 200 000), the number of elements of the ai sequence. In the second line, there is a sequence of n positive integers ai (1 ≤ ai ≤ 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 ji and wi (1 ≤ ji, wi ≤ n for 1 ≤ i ≤ m), separated by single spaces and meaning that ji-th element of the sequence becomes wi. The operations take place in turns, so the i-th modification is applied to the sequence altered by (i − 1) previous modifications.

Output

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 pi ≤ ai for each i (for the original ai 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.

Example

For the input data:

5
3 4 3 2 5
2
5 4
1 5

the correct result is:

TAK
NIE
TAK

Explanation of the example. For the original ai sequence, the condition is satisfied by permutation 2, 4, 3, 1, 5. After the first modification, the sequence becomes 3, 4, 3, 2, 4 and for this sequence no valid permutation exists. After the second modification, the sequence is 5, 4, 3, 2, 4. An example of a permutation p satisfying all constraints for this sequence is 5, 1, 3, 2, 4.


Added by:Race with time
Date:2009-05-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Algorithmic Engagements 2009

hide comments
2021-10-15 21:30:20
Very nice idea :)
2012-05-30 06:55:28 Adrian Jaskó³ka
Time limit is too strict. At Algorithmic Engagements I had AC, but here TL. Only fast I/O helped me to get AC.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.