순열

양의 정수로 이루어진 수열 $a_1, a_2, \ldots, a_n$이 주어진다. $1$번 자리부터 $n$번 자리까지에 $1$부터 $n$까지의 수를 한 번씩 배치하되, $i$번째 자리에 놓는 수는 $a_i$를 넘을 수 없다. 즉, 모든 $1 \le i \le n$에 대해 $p_i \le a_i$를 만족하는, $1$부터 $n$까지의 순열 $p$가 존재하는지 판별한다.

처음 주어진 수열에 대해, 그리고 수열을 한 번씩 수정할 때마다, 그러한 순열을 만들 수 있는지 없는지를 출력하는 프로그램을 작성하시오.

첫째 줄에 수열의 크기 $n$ ($1 \le n \le 200{,}000$)이 주어진다. 둘째 줄에는 $a_1, a_2, \ldots, a_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를 출력한다.

첫째 줄은 처음 주어진 수열에 대한 결과이고, 다음 $m$개의 줄은 각각 $1$번째부터 $m$번째 수정이 적용된 직후의 결과이다.

예제에서, 처음 주어진 수열로는 순열 $2, 4, 3, 1, 5$를 만들 수 있다. 첫 번째 수정 이후 수열은 $3, 4, 3, 2, 4$가 되며, 이 수열로는 어떤 순열도 만들 수 없다. 두 번째 수정 이후 수열은 $5, 4, 3, 2, 4$가 되며, 예를 들어 순열 $5, 1, 3, 2, 4$를 만들 수 있다.