시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 9 5 5 83.333%

문제

승현이는 N개의 돌을 주워서 무게가 증가하는 순서대로 놓았습니다. 두 돌의 무게가 같은 경우는 없습니다. 가장 가벼운 돌에게는 1순위, 두 번째로 가벼운 돌에게는 2순위, ..., 가장 무거운 돌에게는 N순위가 주어졌습니다.

승현이에게는 양팔 저울이 있어서 모든 돌을 양팔 저울 위에 임의의 순서대로 놓기로 했습니다. 승현이가 어떤 순서대로 저울의 어떤 접시에 돌을 놓을 것인지는 알려져 있습니다.

여러분은 승현이가 돌을 얹을 때마다 저울이 어느 쪽으로 기우는지 알아내는 프로그램을 작성해야 합니다. 승현이는 각 돌의 정확한 무게를 알려주지 않습니다.

입력

첫 번째 줄에 돌의 수 N (1≤N≤100, 000)이 주어집니다. 다음 N개 줄에는 두 개의 정수 R(1≤R≤N)과 S(1≤S≤2)이 주어집니다. R은 저울에 얹을 돌의 순위이고 S는 돌을 얹을 저울의 접시 번호입니다. 모든 R은 서로 다릅니다.

출력

저울에 돌을 얹을 때마다, 만약 저울이 1번 접시 쪽으로 기울면(1번 쪽이 더 무거우면) >를, 2번 접시 쪽으로 기울면(2번 쪽이 더 무거우면) <를, 어느 쪽이 더 무거운지 확실히 할 수 없다면 ?를 출력합니다.

예제 입력 1

5
1 2
3 1
2 1
4 2
5 1

예제 출력 1

<
>
>
?
>

힌트

W3sicHJvYmxlbV9pZCI6IjExODMzIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViM2NjIFx1YmIzNFx1YWM4YyBcdWM3YWNcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJiOVx1ZDYwNFx1Yzc3NFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YjNjY1x1Yzc0NCBcdWM4ZmNcdWM2Y2NcdWMxMWMgXHViYjM0XHVhYzhjXHVhYzAwIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViMTkzXHVjNTU4XHVjMmI1XHViMmM4XHViMmU0LiBcdWI0NTAgXHViM2NjXHVjNzU4IFx1YmIzNFx1YWM4Y1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YzJiNVx1YjJjOFx1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YWMwMFx1YmNiY1x1YzZiNCBcdWIzY2NcdWM1ZDBcdWFjOGNcdWIyOTQgMVx1YzIxY1x1YzcwNCwgXHViNDUwIFx1YmM4OFx1YzlmOFx1Yjg1YyBcdWFjMDBcdWJjYmNcdWM2YjQgXHViM2NjXHVjNWQwXHVhYzhjXHViMjk0IDJcdWMyMWNcdWM3MDQsIC4uLiwgXHVhYzAwXHVjN2E1IFx1YmIzNFx1YWM3MFx1YzZiNCBcdWIzY2NcdWM1ZDBcdWFjOGNcdWIyOTQgTlx1YzIxY1x1YzcwNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJiOVx1ZDYwNFx1Yzc3NFx1YzVkMFx1YWM4Y1x1YjI5NCBcdWM1OTFcdWQzMTQgXHVjODAwXHVjNmI4XHVjNzc0IFx1Yzc4OFx1YzViNFx1YzExYyBcdWJhYThcdWI0ZTAgXHViM2NjXHVjNzQ0IFx1YzU5MVx1ZDMxNCBcdWM4MDBcdWM2YjggXHVjNzA0XHVjNWQwIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViMTkzXHVhZTMwXHViODVjIFx1ZDU4OFx1YzJiNVx1YjJjOFx1YjJlNC4gXHVjMmI5XHVkNjA0XHVjNzc0XHVhYzAwIFx1YzViNFx1YjVhNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjODAwXHVjNmI4XHVjNzU4IFx1YzViNFx1YjVhNCBcdWM4MTFcdWMyZGNcdWM1ZDAgXHViM2NjXHVjNzQ0IFx1YjE5M1x1Yzc0NCBcdWFjODNcdWM3NzhcdWM5YzBcdWIyOTQgXHVjNTRjXHViODI0XHVjODM4IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHViN2VjXHViZDg0XHVjNzQwIFx1YzJiOVx1ZDYwNFx1Yzc3NFx1YWMwMCBcdWIzY2NcdWM3NDQgXHVjNWI5XHVjNzQ0IFx1YjU0Y1x1YjljOFx1YjJlNCBcdWM4MDBcdWM2YjhcdWM3NzQgXHVjNWI0XHViMjkwIFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFlMzBcdWM2YjBcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NzRcdWM1N2MgXHVkNTY5XHViMmM4XHViMmU0LiBcdWMyYjlcdWQ2MDRcdWM3NzRcdWIyOTQgXHVhYzAxIFx1YjNjY1x1Yzc1OCBcdWM4MTVcdWQ2NTVcdWQ1NWMgXHViYjM0XHVhYzhjXHViOTdjIFx1YzU0Y1x1YjgyNFx1YzhmY1x1YzljMCBcdWM1NGFcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzY2NcdWM3NTggXHVjMjE4IE4gKDEmbGU7TiZsZTsxMDAsIDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggUigxJmxlO1ImbGU7TilcdWFjZmMgUygxJmxlO1MmbGU7MilcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBSXHVjNzQwIFx1YzgwMFx1YzZiOFx1YzVkMCBcdWM1YjlcdWM3NDQgXHViM2NjXHVjNzU4IFx1YzIxY1x1YzcwNFx1Yzc3NFx1YWNlMCBTXHViMjk0IFx1YjNjY1x1Yzc0NCBcdWM1YjlcdWM3NDQgXHVjODAwXHVjNmI4XHVjNzU4IFx1YzgxMVx1YzJkYyBcdWJjODhcdWQ2MzhcdWM3ODVcdWIyYzhcdWIyZTQuIFx1YmFhOFx1YjRlMCBSXHVjNzQwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5ODVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjODAwXHVjNmI4XHVjNWQwIFx1YjNjY1x1Yzc0NCBcdWM1YjlcdWM3NDQgXHViNTRjXHViOWM4XHViMmU0LCBcdWI5Y2NcdWM1N2QgXHVjODAwXHVjNmI4XHVjNzc0IDFcdWJjODggXHVjODExXHVjMmRjIFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFlMzBcdWM2YjhcdWJhNzQoMVx1YmM4OCBcdWNhYmRcdWM3NzQgXHViMzU0IFx1YmIzNFx1YWM3MFx1YzZiMFx1YmE3NCkgPHN0cm9uZz4mZ3Q7PFwvc3Ryb25nPlx1Yjk3YywgMlx1YmM4OCBcdWM4MTFcdWMyZGMgXHVjYWJkXHVjNzNjXHViODVjIFx1YWUzMFx1YzZiOFx1YmE3NCgyXHViYzg4IFx1Y2FiZFx1Yzc3NCBcdWIzNTQgXHViYjM0XHVhYzcwXHVjNmIwXHViYTc0KSA8c3Ryb25nPiZsdDs8XC9zdHJvbmc+XHViOTdjLCBcdWM1YjRcdWIyOTAgXHVjYWJkXHVjNzc0IFx1YjM1NCBcdWJiMzRcdWFjNzBcdWM2YjRcdWM5YzAgXHVkNjU1XHVjMmU0XHVkNzg4IFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0IDxzdHJvbmc+PzxcL3N0cm9uZz5cdWI5N2MgXHVjZDljXHViODI1XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExODMzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiV2VpZ2h0aW5nIHN0b25lcyIsImRlc2NyaXB0aW9uIjoiPHA+SmFjayBzb21laG93IGZvdW5kIE4gc3RvbmVzIGFuZCBhcnJhbmdlZCB0aGVtIGluIGluY3JlYXNpbmcgb3JkZXIgb2YgdGhlaXIgd2VpZ2h0cy4gTm8gdHdvIHdlaWdodHMgYXJlIGVxdWFsLiBUaGUgbGlnaHRlc3Qgc3RvbmUgaXMgZ2l2ZW4gdGhlIHJhbmsgMSwgdGhlIG5leHQgbGlnaHRlc3QgJm1kYXNoOyAyLCBhbmQgc28gb24sIHRoZSBoZWF2aWVzdCBzdG9uZSBnZXRzIHRoZSByYW5rIE4uPFwvcD5cclxuXHJcbjxwPkhlIGhhcyBhIGJhbGFuY2Ugc2NhbGUgYW5kIGRlY2lkZWQgdG8gcHV0IGFsbCB0aGUgc3RvbmVzIG9uIGl0JnJzcXVvO3Mgc2lkZXMgaW4gc29tZSBvcmRlci4gSXQmcnNxdW87cyBrbm93biBpbiB3aGljaCBvcmRlciBoZSBpcyBnb2luZyB0byBwdXQgdGhvc2Ugc3RvbmVzIG9uIHRoZSBzY2FsZSBhbmQgb24gd2hpY2ggc2lkZSBlYWNoIHN0b25lIGdldHMuPFwvcD5cclxuXHJcbjxwPllvdSBoYXZlIHRvIGRldGVybWluZSB0aGUgc3RhdGUgb2Ygc2NhbGUgYWZ0ZXIgZWFjaCBzdG9uZSBpcyBhZGRlZC4gSmFjayBkb2VzbiZyc3F1bzt0IHRlbGwgdGhlIGV4YWN0IHdlaWdodHMgb2YgdGhvc2Ugc3RvbmVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgaW50ZWdlciBudW1iZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAwMDApLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXIgbnVtYmVyczogUiAoMSAmbGU7IFIgJmxlOyBOKSBhbmQgUyAoMSAmbGU7IFMgJmxlOyAyKS4gUiBpcyB0aGUgcmFuayBvZiB0aGUgbmV4dCBzdG9uZSB3aGljaCBpcyBwdXQgb24gc2lkZSBTLiBBbGwgUiZyc3F1bztzIHdpbGwgYmUgZGlzdGluY3QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IE4gbGluZXMgJm1kYXNoOyBvbmUgZm9yIGVhY2ggYWRkZWQgc3RvbmUuIElmIGFmdGVyIGFkZGluZyB0aGUgY29ycmVzcG9uZGluZyBzdG9uZSBzaWRlIDEgaXMgaGVhdmllciwgb3V0cHV0ICZsZHF1bzsmbHQ7JnJkcXVvOy4gSWYgc2lkZSAyIGlzIGhlYXZpZXIsIG91dHB1dCAmbGRxdW87Jmd0OyZyZHF1bzsuIElmIGl0JnJzcXVvO3Mgbm90IGNsZWFyIGluIHdoaWNoIHN0YXRlIHRoZSBzY2FsZSB3aWxsIGJlLCBvdXRwdXQgJmxkcXVvOz8mcmRxdW87LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > International Zhautykov Olympiad > IZhO 2011 D번