시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB112302350.000%

문제

양의 정수로 이루어진 수열 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개 줄에는 각각의 수정이 이루어진 후에 순열을 만들 수 있는지를 출력한다.

예제 입력 1

5
3 4 3 2 5
2
5 4
1 5

예제 출력 1

TAK
NIE
TAK

힌트

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

W3sicHJvYmxlbV9pZCI6IjgzMzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMWNcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNCBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIC4uLiwgYTxzdWI+bjxcL3N1Yj5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMsIDFcdWJjODhcdWJkODBcdWQxMzAgblx1YmM4OFx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YmMxNFx1YWZiOFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgaVx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgYTxzdWI+aTxcL3N1Yj5cdWJjZjRcdWIyZTQgXHVkMDZjXHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIFx1Yzk4OSwgXHViYWE4XHViNGUwIDEgJmxlOyBpICZsZTsgblx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgcDxzdWI+aTxcL3N1Yj4gJmxlOyBhPHN1Yj5pPFwvc3ViPlx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMWNcdWM1ZjQgcFx1Yjk3YyBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZGY4XHViOWFjXHVhY2UwIFx1YWRmOCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjMjE4XHVjODE1XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVhYzAxXHVhYzAxIFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzBcdWI5N2MgXHVkMzEwXHViY2M0XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgbiAoMSAmbGU7IG4gJmxlOyAyMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgYTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWMyMThcdWM4MTVcdWQ1NWMgXHVkNjlmXHVjMjE4IG0gKDAgJmxlOyBtICZsZTsgNTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzViNFx1YjViYlx1YWM4YyBcdWMyMThcdWM4MTVcdWQ1ODhcdWIyOTRcdWM5YzAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWI0NTAgXHVjODE1XHVjMjE4IGo8c3ViPmk8XC9zdWI+XHVjNjQwIHc8c3ViPmk8XC9zdWI+XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuICgxICZsZTsgajxzdWI+aTxcL3N1Yj4sIHc8c3ViPmk8XC9zdWI+ICZsZTsgbikgajxzdWI+aTxcL3N1Yj5cdWJjODhcdWM5ZjggXHVjNmQwXHVjMThjXHViOTdjIHc8c3ViPmk8XC9zdWI+XHViODVjIFx1YzIxOFx1YzgxNVx1ZDU4OFx1YjJlNFx1YjI5NCBcdWM3NzRcdWJiZjhcdWM3NzRcdWIyZTQuIFx1YzIxOFx1YzgxNVx1Yzc0MCBcdWIyMDRcdWM4MDFcdWQ1NzRcdWMxMWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWM5ODksIGlcdWJjODhcdWM5ZjggXHVjMjE4XHVjODE1XHVjNzQwIChpLTEpXHViYzg4IFx1YzIxOFx1YzgxNVx1YjQxYyBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWNkMWQgbSsxXHVjOTA0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBUQUtcdWM3NDQsIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHVjNzNjXHViYTc0IE5JRVx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNWQwIFx1YjlkZVx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzBcdWI5N2MsIFx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMjE4XHVjODE1XHVjNzc0IFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQ2YzRcdWM1ZDAgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzIxY1x1YzVmNCAyLCA0LCAzLCAxLCA1XHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIxOFx1YzgxNSBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVjMjE4XHVjNWY0XHVjNzQwIDMsIDQsIDMsIDIsIDRcdWFjMDAgXHViNDE4XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHVjNWY0XHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc0MCBcdWM1YzZcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMjE4XHVjODE1IFx1Yzc3NFx1ZDZjNFx1YzVkMCBcdWMyMThcdWM1ZjRcdWM3NDAgNSwgNCwgMywgMiwgNFx1YWMwMCBcdWI0MThcdWFjZTAsIFx1Yzc3NFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzQwIDUsIDEsIDMsIDIsIDRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI4MzMwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGVybXV0YXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSBzZXF1ZW5jZSBvZiBwb3NpdGl2ZSBpbnRlZ2VycyBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIC4uLiwgYTxzdWI+bjxcL3N1Yj4uIFdlIHdvdWxkIGxpa2UgdG8gb3JkZXIgdGhlIG51bWJlcnMgZnJvbSAxIHRvIG4gaW4gc3VjaCBhIHdheSwgdGhhdCB0aGUgaS10aCBudW1iZXIgaXMgbm90IGdyZWF0ZXIgdGhhbiBhPHN1Yj5pPFwvc3ViPiAoZm9yIGVhY2ggaSkuIEluIG90aGVyIHdvcmRzLCB3ZSBhcmUgbG9va2luZyBmb3IgYSBwZXJtdXRhdGlvbiBwIG9mIG51bWJlcnMgZnJvbSAxIHRvIG4sIHdoaWNoIHNhdGlzZmllczogcDxzdWI+aTxcL3N1Yj4gJmxlOyBhPHN1Yj5pPFwvc3ViPiBmb3IgZWFjaCAxICZsZTsgaSAmbGU7IG4uIFRoZXJlIGlzIG9uZSBtb3JlIHByb2JsZW0sIHRoZSBzZXF1ZW5jZSBhaSBtYXkgY2hhbmdlIG92ZXIgdGltZS4uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2Ygc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAyMDAgMDAwKSwgdGhlIG51bWJlciBvZiBlbGVtZW50cyBvZiB0aGUgYWkgc2VxdWVuY2UuIEluIHRoZSBzZWNvbmQgbGluZSwgdGhlcmUgaXMgYSBzZXF1ZW5jZSBvZiBuIHBvc2l0aXZlIGludGVnZXJzIGE8c3ViPmk8XC9zdWI+ICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyBuKSwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIFRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIG0gKDAgJmxlOyBtICZsZTsgNTAwIDAwMCksIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIG1vZGlmaWNhdGlvbnMgbWFkZSB0byB0aGUgYTxzdWI+aTxcL3N1Yj4gc2VxdWVuY2UuIFRoZSBmb2xsb3dpbmcgbSBsaW5lcyBkZXNjcmliZSB0aGVzZSBtb2RpZmljYXRpb25zLiBFYWNoIGRlc2NyaXB0aW9uIGNvbnNpc3RzIG9mIHR3byBpbnRlZ2VycyBqPHN1Yj5pPFwvc3ViPiBhbmQgdzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBqPHN1Yj5pPFwvc3ViPiwgdzxzdWI+aTxcL3N1Yj4gJmxlOyBuIGZvciAxICZsZTsgaSAmbGU7IG0pLCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcyBhbmQgbWVhbmluZyB0aGF0IGo8c3ViPmk8XC9zdWI+LXRoIGVsZW1lbnQgb2YgdGhlIHNlcXVlbmNlIGJlY29tZXMgdzxzdWI+aTxcL3N1Yj4uIFRoZSBvcGVyYXRpb25zIHRha2UgcGxhY2UgaW4gdHVybnMsIHNvIHRoZSBpLXRoIG1vZGlmaWNhdGlvbiBpcyBhcHBsaWVkIHRvIHRoZSBzZXF1ZW5jZSBhbHRlcmVkIGJ5IChpLTEpIHByZXZpb3VzIG1vZGlmaWNhdGlvbnMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIHNob3VsZCBvdXRwdXQgZXhhY3RseSBtKzEgbGluZXMgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC4gRWFjaCBvZiB0aG9zZSBsaW5lcyBzaG91bGQgY29udGFpbiBvbmUgd29yZCBUQUsgKG1lYW5pbmcgWUVTKSBvciBOSUUgKG1lYW5pbmcgTk8pLiBUaGUgd29yZCBpbiB0aGUgZmlyc3QgbGluZSBzaG91bGQgdGVsbCBpZiB0aGVyZSBleGlzdHMgYSBwZXJtdXRhdGlvbiBwLCB3aGljaCBzYXRpc2ZpZXMgcDxzdWI+aTxcL3N1Yj4gJmxlOyBhPHN1Yj5pPFwvc3ViPiBmb3IgZWFjaCBpIChmb3IgdGhlIG9yaWdpbmFsIGFpIHNlcXVlbmNlKSwgd2hlcmVhcyB0aGUgd29yZHMgZnJvbSBmb2xsb3dpbmcgbGluZXMgYW5zd2VyIHRoZSBxdWVzdGlvbiB3aGV0aGVyIHRoZXJlIGV4aXN0IGFueSAocG90ZW50aWFsbHkgZGlmZmVyZW50KSBwZXJtdXRhdGlvbnMgdGhhdCBzYXRpc2Z5IHRoZSBnaXZlbiBjb25kaXRpb25zIGZvciB0aGUgYWkgc2VxdWVuY2UgYWZ0ZXIgZWFjaCBtb2RpZmljYXRpb24uPFwvcD5cclxuIiwiaGludCI6IjxwPkZvciB0aGUgb3JpZ2luYWwgYTxzdWI+aTxcL3N1Yj4gc2VxdWVuY2UsIHRoZSBjb25kaXRpb24gaXMgc2F0aXNmaWVkIGJ5IHBlcm11dGF0aW9uIDIsIDQsIDMsIDEsIDUuIEFmdGVyIHRoZSBmaXJzdCBtb2RpZmljYXRpb24sIHRoZSBzZXF1ZW5jZSBiZWNvbWVzIDMsIDQsIDMsIDIsIDQgYW5kIGZvciB0aGlzIHNlcXVlbmNlIG5vIHZhbGlkIHBlcm11dGF0aW9uIGV4aXN0cy4gQWZ0ZXIgdGhlIHNlY29uZCBtb2RpZmljYXRpb24sIHRoZSBzZXF1ZW5jZSBpcyA1LCA0LCAzLCAyLCA0LiBBbiBleGFtcGxlIG9mIGEgcGVybXV0YXRpb24gcCBzYXRpc2Z5aW5nIGFsbCBjb25zdHJhaW50cyBmb3IgdGhpcyBzZXF1ZW5jZSBpcyA1LCAxLCAzLCAyLCA0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Algorithmic Engagements > PA 2009 5-3번