시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 33 8 8 53.333%

문제

양의 정수로 이루어진 수열 a1, a2, ..., an이 주어진다. 여기서, 1번부터 n번까지 숫자의 순서를 바꾸려고 한다. 이 때, i번째 숫자는 ai보다 크면 안된다. 즉, 모든 1 ≤ i ≤ n에 대해서 pi ≤ ai을 만족하는 1부터 n까지 이루어진 순열 p를 찾아야 한다.

수열이 주어졌을 때, 그리고 그 수열을 수정했을 때, 각각 순열을 만들 수 있는지 없는지를 판별하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 n (1 ≤ n ≤ 200,000)이 주어진다. 둘째 줄에는 ai가 주어진다. 셋째 줄에는 수열을 수정한 횟수 m (0 ≤ m ≤ 500,000)이 주어진다. 다음 m개 줄에는 수열을 어떻게 수정했는지 한 줄에 하나씩 주어지며, 두 정수 ji와 wi로 이루어져 있다. (1 ≤ ji, wi ≤ n) ji번째 원소를 wi로 수정했다는 이미이다. 수정은 누적해서 이루어진다. 즉, i번째 수정은 (i-1)번 수정된 수열에서 이루어진다.

출력

출력은 총 m+1줄이다. 각 줄마다 순열을 만들 수 있으면 TAK을, 만들 수 없으면 NIE를 출력해야 한다.

첫째 줄에는 입력으로 주어진 수열을 이용해 문제의 조건에 맞는 순열을 만들 수 있는지를, 다음 m개 줄에는 각각의 수정이 이루어진 후에 순열을 만들 수 있는지를 출력한다.

예제 입력

5
3 4 3 2 5
2
5 4
1 5

예제 출력

TAK
NIE
TAK

힌트

입력으로 주어진 수열을 이용해서 순열 2, 4, 3, 1, 5를 만들 수 있다. 첫 번째 수정 이후에 수열은 3, 4, 3, 2, 4가 되고, 이 수열로 만들 수 있는 순열은 없다. 두 번째 수정 이후에 수열은 5, 4, 3, 2, 4가 되고, 이를 이용해 만들 수 있는 순열은 5, 1, 3, 2, 4이다.

출처

Contest > Algorithmic Engagements > PA 2009 11번