시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+bjxcL3N1Yj5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMsIDFcdWJjODhcdWJkODBcdWQxMzAgblx1YmM4OFx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YmMxNFx1YWZiOFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgaVx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgYTxzdWI+aTxcL3N1Yj5cdWJjZjRcdWIyZTQgXHVkMDZjXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWJhYThcdWI0ZTAgMSAmbGU7IGkgJmxlOyBuXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBwPHN1Yj5pPFwvc3ViPiAmbGU7IGE8c3ViPmk8XC9zdWI+XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCAxXHViZDgwXHVkMTMwIG5cdWFlNGNcdWM5YzAgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YzIxY1x1YzVmNCBwXHViOTdjIFx1Y2MzZVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWMyMThcdWM4MTVcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWFjMDFcdWFjMDEgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YzVjNlx1YjI5NFx1YzljMFx1Yjk3YyBcdWQzMTBcdWJjYzRcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMCBuICgxICZsZTsgbiAmbGU7IDIwMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBhPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzE0Ylx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzIxOFx1YzgxNVx1ZDU1YyBcdWQ2OWZcdWMyMTggbSAoMCAmbGU7IG0gJmxlOyA1MDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YzIxOFx1YzgxNVx1ZDU4OFx1YjI5NFx1YzljMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YjQ1MCBcdWM4MTVcdWMyMTggajxzdWI+aTxcL3N1Yj5cdWM2NDAgdzxzdWI+aTxcL3N1Yj5cdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDEgJmxlOyBqPHN1Yj5pPFwvc3ViPiwgdzxzdWI+aTxcL3N1Yj4gJmxlOyBuKSBqPHN1Yj5pPFwvc3ViPlx1YmM4OFx1YzlmOCBcdWM2ZDBcdWMxOGNcdWI5N2MgdzxzdWI+aTxcL3N1Yj5cdWI4NWMgXHVjMjE4XHVjODE1XHVkNTg4XHViMmU0XHViMjk0IFx1Yzc3NFx1YmJmOFx1Yzc3NFx1YjJlNC4gXHVjMjE4XHVjODE1XHVjNzQwIFx1YjIwNFx1YzgwMVx1ZDU3NFx1YzExYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzk4OSwgaVx1YmM4OFx1YzlmOCBcdWMyMThcdWM4MTVcdWM3NDAgKGktMSlcdWJjODggXHVjMjE4XHVjODE1XHViNDFjIFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1Y2QxZCBtKzFcdWM5MDRcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWI5YzhcdWIyZTQgXHVjMjFjXHVjNWY0XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTc0IFRBS1x1Yzc0NCwgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWM3M2NcdWJhNzQgTklFXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM1ZDAgXHViOWRlXHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMFx1Yjk3YywgXHViMmU0XHVjNzRjIG1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyMThcdWM4MTVcdWM3NzQgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1ZDZjNFx1YzVkMCBcdWMyMWNcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NzRcdWMxMWMgXHVjMjFjXHVjNWY0IDIsIDQsIDMsIDEsIDVcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjE4XHVjODE1IFx1Yzc3NFx1ZDZjNFx1YzVkMCBcdWMyMThcdWM1ZjRcdWM3NDAgMywgNCwgMywgMiwgNFx1YWMwMCBcdWI0MThcdWFjZTAsIFx1Yzc3NCBcdWMyMThcdWM1ZjRcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMjFjXHVjNWY0XHVjNzQwIFx1YzVjNlx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMThcdWM4MTUgXHVjNzc0XHVkNmM0XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc0MCA1LCA0LCAzLCAyLCA0XHVhYzAwIFx1YjQxOFx1YWNlMCwgXHVjNzc0XHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyMWNcdWM1ZjRcdWM3NDAgNSwgMSwgMywgMiwgNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjgzMzAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQZXJtdXRhdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBhIHNlcXVlbmNlIG9mIHBvc2l0aXZlIGludGVnZXJzIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPi4gV2Ugd291bGQgbGlrZSB0byBvcmRlciB0aGUgbnVtYmVycyBmcm9tIDEgdG8gbiBpbiBzdWNoIGEgd2F5LCB0aGF0IHRoZSBpLXRoIG51bWJlciBpcyBub3QgZ3JlYXRlciB0aGFuIGE8c3ViPmk8XC9zdWI+IChmb3IgZWFjaCBpKS4gSW4gb3RoZXIgd29yZHMsIHdlIGFyZSBsb29raW5nIGZvciBhIHBlcm11dGF0aW9uIHAgb2YgbnVtYmVycyBmcm9tIDEgdG8gbiwgd2hpY2ggc2F0aXNmaWVzOiBwPHN1Yj5pPFwvc3ViPiAmbGU7IGE8c3ViPmk8XC9zdWI+IGZvciBlYWNoIDEgJmxlOyBpICZsZTsgbi4gVGhlcmUgaXMgb25lIG1vcmUgcHJvYmxlbSwgdGhlIHNlcXVlbmNlIGFpIG1heSBjaGFuZ2Ugb3ZlciB0aW1lLi4uPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2Ygc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgb25lIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAyMDAgMDAwKSwgdGhlIG51bWJlciBvZiBlbGVtZW50cyBvZiB0aGUgYWkgc2VxdWVuY2UuIEluIHRoZSBzZWNvbmQgbGluZSwgdGhlcmUgaXMgYSBzZXF1ZW5jZSBvZiBuIHBvc2l0aXZlIGludGVnZXJzIGE8c3ViPmk8XC9zdWI+ICgxICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyBuKSwgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMuIFRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIG0gKDAgJmxlOyBtICZsZTsgNTAwIDAwMCksIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIG1vZGlmaWNhdGlvbnMgbWFkZSB0byB0aGUgYTxzdWI+aTxcL3N1Yj4gc2VxdWVuY2UuIFRoZSBmb2xsb3dpbmcgbSBsaW5lcyBkZXNjcmliZSB0aGVzZSBtb2RpZmljYXRpb25zLiBFYWNoIGRlc2NyaXB0aW9uIGNvbnNpc3RzIG9mIHR3byBpbnRlZ2VycyBqPHN1Yj5pPFwvc3ViPiBhbmQgdzxzdWI+aTxcL3N1Yj4gKDEgJmxlOyBqPHN1Yj5pPFwvc3ViPiwgdzxzdWI+aTxcL3N1Yj4gJmxlOyBuIGZvciAxICZsZTsgaSAmbGU7IG0pLCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlcyBhbmQgbWVhbmluZyB0aGF0IGo8c3ViPmk8XC9zdWI+LXRoIGVsZW1lbnQgb2YgdGhlIHNlcXVlbmNlIGJlY29tZXMgdzxzdWI+aTxcL3N1Yj4uIFRoZSBvcGVyYXRpb25zIHRha2UgcGxhY2UgaW4gdHVybnMsIHNvIHRoZSBpLXRoIG1vZGlmaWNhdGlvbiBpcyBhcHBsaWVkIHRvIHRoZSBzZXF1ZW5jZSBhbHRlcmVkIGJ5IChpLTEpIHByZXZpb3VzIG1vZGlmaWNhdGlvbnMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBzaG91bGQgb3V0cHV0IGV4YWN0bHkgbSsxIGxpbmVzIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuIEVhY2ggb2YgdGhvc2UgbGluZXMgc2hvdWxkIGNvbnRhaW4gb25lIHdvcmQgVEFLIChtZWFuaW5nIFlFUykgb3IgTklFIChtZWFuaW5nIE5PKS4gVGhlIHdvcmQgaW4gdGhlIGZpcnN0IGxpbmUgc2hvdWxkIHRlbGwgaWYgdGhlcmUgZXhpc3RzIGEgcGVybXV0YXRpb24gcCwgd2hpY2ggc2F0aXNmaWVzIHA8c3ViPmk8XC9zdWI+ICZsZTsgYTxzdWI+aTxcL3N1Yj4gZm9yIGVhY2ggaSAoZm9yIHRoZSBvcmlnaW5hbCBhaSBzZXF1ZW5jZSksIHdoZXJlYXMgdGhlIHdvcmRzIGZyb20gZm9sbG93aW5nIGxpbmVzIGFuc3dlciB0aGUgcXVlc3Rpb24gd2hldGhlciB0aGVyZSBleGlzdCBhbnkgKHBvdGVudGlhbGx5IGRpZmZlcmVudCkgcGVybXV0YXRpb25zIHRoYXQgc2F0aXNmeSB0aGUgZ2l2ZW4gY29uZGl0aW9ucyBmb3IgdGhlIGFpIHNlcXVlbmNlIGFmdGVyIGVhY2ggbW9kaWZpY2F0aW9uLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+Rm9yIHRoZSBvcmlnaW5hbCBhPHN1Yj5pPFwvc3ViPiBzZXF1ZW5jZSwgdGhlIGNvbmRpdGlvbiBpcyBzYXRpc2ZpZWQgYnkgcGVybXV0YXRpb24gMiwgNCwgMywgMSwgNS4gQWZ0ZXIgdGhlIGZpcnN0IG1vZGlmaWNhdGlvbiwgdGhlIHNlcXVlbmNlIGJlY29tZXMgMywgNCwgMywgMiwgNCBhbmQgZm9yIHRoaXMgc2VxdWVuY2Ugbm8gdmFsaWQgcGVybXV0YXRpb24gZXhpc3RzLiBBZnRlciB0aGUgc2Vjb25kIG1vZGlmaWNhdGlvbiwgdGhlIHNlcXVlbmNlIGlzIDUsIDQsIDMsIDIsIDQuIEFuIGV4YW1wbGUgb2YgYSBwZXJtdXRhdGlvbiBwIHNhdGlzZnlpbmcgYWxsIGNvbnN0cmFpbnRzIGZvciB0aGlzIHNlcXVlbmNlIGlzIDUsIDEsIDMsIDIsIDQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Algorithmic Engagements > PA 2009 5-3번