시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 52 11 10 58.824%

문제

양의 정수로 이루어진 수열 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+bjxcL3N1Yj5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMsIDFcdWJjODhcdWJkODBcdWQxMzAgblx1YmM4OFx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YmMxNFx1YWZiOFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIGlcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IGE8c3ViPmk8XC9zdWI+XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuIFx1Yzk4OSwgXHViYWE4XHViNGUwIDEgJmxlOyBpICZsZTsgblx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgcDxzdWI+aTxcL3N1Yj4gJmxlOyBhPHN1Yj5pPFwvc3ViPlx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMWNcdWM1ZjQgcFx1Yjk3YyBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhZGY4XHViOWFjXHVhY2UwIFx1YWRmOCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjMjE4XHVjODE1XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVhYzAxXHVhYzAxIFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWM1YzZcdWIyOTRcdWM5YzBcdWI5N2MgXHVkMzEwXHViY2M0XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzAgbiAoMSAmbGU7IG4gJmxlOyAyMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgYTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMxNGJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWMyMThcdWM4MTVcdWQ1NWMgXHVkNjlmXHVjMjE4IG0gKDAgJmxlOyBtICZsZTsgNTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgbVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzViNFx1YjViYlx1YWM4YyBcdWMyMThcdWM4MTVcdWQ1ODhcdWIyOTRcdWM5YzAgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWI0NTAgXHVjODE1XHVjMjE4IGo8c3ViPmk8XC9zdWI+XHVjNjQwIHc8c3ViPmk8XC9zdWI+XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuICgxICZsZTsgajxzdWI+aTxcL3N1Yj4sIHc8c3ViPmk8XC9zdWI+ICZsZTsgbikgajxzdWI+aTxcL3N1Yj5cdWJjODhcdWM5ZjggXHVjNmQwXHVjMThjXHViOTdjIHc8c3ViPmk8XC9zdWI+XHViODVjIFx1YzIxOFx1YzgxNVx1ZDU4OFx1YjJlNFx1YjI5NCBcdWM3NzRcdWJiZjhcdWM3NzRcdWIyZTQuIFx1YzIxOFx1YzgxNVx1Yzc0MCBcdWIyMDRcdWM4MDFcdWQ1NzRcdWMxMWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWM5ODksIGlcdWJjODhcdWM5ZjggXHVjMjE4XHVjODE1XHVjNzQwIChpLTEpXHViYzg4IFx1YzIxOFx1YzgxNVx1YjQxYyBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWNkMWQgbSsxXHVjOTA0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBUQUtcdWM3NDQsIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHVjNzNjXHViYTc0IE5JRVx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNWQwIFx1YjlkZVx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzBcdWI5N2MsIFx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjMjE4XHVjODE1XHVjNzc0IFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQ2YzRcdWM1ZDAgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzIxY1x1YzVmNCAyLCA0LCAzLCAxLCA1XHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIxOFx1YzgxNSBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVjMjE4XHVjNWY0XHVjNzQwIDMsIDQsIDMsIDIsIDRcdWFjMDAgXHViNDE4XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHVjNWY0XHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc0MCBcdWM1YzZcdWIyZTQuIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMjE4XHVjODE1IFx1Yzc3NFx1ZDZjNFx1YzVkMCBcdWMyMThcdWM1ZjRcdWM3NDAgNSwgNCwgMywgMiwgNFx1YWMwMCBcdWI0MThcdWFjZTAsIFx1Yzc3NFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NzQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzQwIDUsIDEsIDMsIDIsIDRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI4MzMwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGVybXV0YXRpb24iLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gYSBzZXF1ZW5jZSBvZiBwb3NpdGl2ZSBpbnRlZ2VycyBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIC4uLiwgYTxzdWI+bjxcL3N1Yj4uIFdlIHdvdWxkIGxpa2UgdG8gb3JkZXIgdGhlIG51bWJlcnMgZnJvbSAxIHRvIG4gaW4gc3VjaCBhIHdheSwgdGhhdCB0aGUgaS10aCBudW1iZXIgaXMgbm90IGdyZWF0ZXIgdGhhbiBhPHN1Yj5pPFwvc3ViPiAoZm9yIGVhY2ggaSkuIEluIG90aGVyIHdvcmRzLCB3ZSBhcmUgbG9va2luZyBmb3IgYSBwZXJtdXRhdGlvbiBwIG9mIG51bWJlcnMgZnJvbSAxIHRvIG4sIHdoaWNoIHNhdGlzZmllczogcDxzdWI+aTxcL3N1Yj4gJmxlOyBhPHN1Yj5pPFwvc3ViPiBmb3IgZWFjaCAxICZsZTsgaSAmbGU7IG4uIFRoZXJlIGlzIG9uZSBtb3JlIHByb2JsZW0sIHRoZSBzZXF1ZW5jZSBhaSBtYXkgY2hhbmdlIG92ZXIgdGltZS4uLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMjAwIDAwMCksIHRoZSBudW1iZXIgb2YgZWxlbWVudHMgb2YgdGhlIGFpIHNlcXVlbmNlLiBJbiB0aGUgc2Vjb25kIGxpbmUsIHRoZXJlIGlzIGEgc2VxdWVuY2Ugb2YgbiBwb3NpdGl2ZSBpbnRlZ2VycyBhPHN1Yj5pPFwvc3ViPiAoMSAmbGU7IGE8c3ViPmk8XC9zdWI+ICZsZTsgbiksIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBUaGUgdGhpcmQgbGluZSBjb250YWlucyBvbmUgaW50ZWdlciBtICgwICZsZTsgbSAmbGU7IDUwMCAwMDApLCByZXByZXNlbnRpbmcgdGhlIG51bWJlciBvZiBtb2RpZmljYXRpb25zIG1hZGUgdG8gdGhlIGE8c3ViPmk8XC9zdWI+IHNlcXVlbmNlLiBUaGUgZm9sbG93aW5nIG0gbGluZXMgZGVzY3JpYmUgdGhlc2UgbW9kaWZpY2F0aW9ucy4gRWFjaCBkZXNjcmlwdGlvbiBjb25zaXN0cyBvZiB0d28gaW50ZWdlcnMgajxzdWI+aTxcL3N1Yj4gYW5kIHc8c3ViPmk8XC9zdWI+ICgxICZsZTsgajxzdWI+aTxcL3N1Yj4sIHc8c3ViPmk8XC9zdWI+ICZsZTsgbiBmb3IgMSAmbGU7IGkgJmxlOyBtKSwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMgYW5kIG1lYW5pbmcgdGhhdCBqPHN1Yj5pPFwvc3ViPi10aCBlbGVtZW50IG9mIHRoZSBzZXF1ZW5jZSBiZWNvbWVzIHc8c3ViPmk8XC9zdWI+LiBUaGUgb3BlcmF0aW9ucyB0YWtlIHBsYWNlIGluIHR1cm5zLCBzbyB0aGUgaS10aCBtb2RpZmljYXRpb24gaXMgYXBwbGllZCB0byB0aGUgc2VxdWVuY2UgYWx0ZXJlZCBieSAoaS0xKSBwcmV2aW91cyBtb2RpZmljYXRpb25zLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gc2hvdWxkIG91dHB1dCBleGFjdGx5IG0rMSBsaW5lcyB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LiBFYWNoIG9mIHRob3NlIGxpbmVzIHNob3VsZCBjb250YWluIG9uZSB3b3JkIFRBSyAobWVhbmluZyBZRVMpIG9yIE5JRSAobWVhbmluZyBOTykuIFRoZSB3b3JkIGluIHRoZSBmaXJzdCBsaW5lIHNob3VsZCB0ZWxsIGlmIHRoZXJlIGV4aXN0cyBhIHBlcm11dGF0aW9uIHAsIHdoaWNoIHNhdGlzZmllcyBwPHN1Yj5pPFwvc3ViPiAmbGU7IGE8c3ViPmk8XC9zdWI+IGZvciBlYWNoIGkgKGZvciB0aGUgb3JpZ2luYWwgYWkgc2VxdWVuY2UpLCB3aGVyZWFzIHRoZSB3b3JkcyBmcm9tIGZvbGxvd2luZyBsaW5lcyBhbnN3ZXIgdGhlIHF1ZXN0aW9uIHdoZXRoZXIgdGhlcmUgZXhpc3QgYW55IChwb3RlbnRpYWxseSBkaWZmZXJlbnQpIHBlcm11dGF0aW9ucyB0aGF0IHNhdGlzZnkgdGhlIGdpdmVuIGNvbmRpdGlvbnMgZm9yIHRoZSBhaSBzZXF1ZW5jZSBhZnRlciBlYWNoIG1vZGlmaWNhdGlvbi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkZvciB0aGUgb3JpZ2luYWwgYTxzdWI+aTxcL3N1Yj4gc2VxdWVuY2UsIHRoZSBjb25kaXRpb24gaXMgc2F0aXNmaWVkIGJ5IHBlcm11dGF0aW9uIDIsIDQsIDMsIDEsIDUuIEFmdGVyIHRoZSBmaXJzdCBtb2RpZmljYXRpb24sIHRoZSBzZXF1ZW5jZSBiZWNvbWVzIDMsIDQsIDMsIDIsIDQgYW5kIGZvciB0aGlzIHNlcXVlbmNlIG5vIHZhbGlkIHBlcm11dGF0aW9uIGV4aXN0cy4gQWZ0ZXIgdGhlIHNlY29uZCBtb2RpZmljYXRpb24sIHRoZSBzZXF1ZW5jZSBpcyA1LCA0LCAzLCAyLCA0LiBBbiBleGFtcGxlIG9mIGEgcGVybXV0YXRpb24gcCBzYXRpc2Z5aW5nIGFsbCBjb25zdHJhaW50cyBmb3IgdGhpcyBzZXF1ZW5jZSBpcyA1LCAxLCAzLCAyLCA0LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Algorithmic Engagements > PA 2009 5-3번