시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 11677 5823 4679 52.846%

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

  1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
  2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음줄에 N개 문서의 중요도가 주어지는데, 중요도는 1 이상 9 이하이다. 중요도가 같은 문서가 여러 개 있을 수도 있다. 위의 예는 N=4, M=0(A문서가 궁금하다면), 중요도는 2 1 4 3이 된다.

출력

각 test case에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

예제 입력 1

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

예제 출력 1

1
2
5
W3sicHJvYmxlbV9pZCI6IjE5NjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1MDRcdWI5YjBcdWQxMzAgXHVkMDUwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1ZWNcdWI3ZWNcdWJkODRcdWIzYzQgXHVjNTRjXHViMmU0XHVjMmRjXHVkNTNjIFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc1OCBcdWQ1MDRcdWI5YjBcdWQxMzAgXHVhZTMwXHVhZTMwXHViMjk0IFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc3NCBcdWM3NzhcdWMxYzRcdWQ1NThcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YmIzOFx1YzExY1x1Yjk3YyBcdWM3NzhcdWMxYzQgXHViYTg1XHViODM5XHVjNzQ0IFx1YmMxYlx1Yzc0MCAmbHNxdW87XHVjMjFjXHVjMTFjXHViMzAwXHViODVjJnJzcXVvOywgXHVjOTg5IFx1YmEzY1x1YzgwMCBcdWM2OTRcdWNjYWRcdWI0MWMgXHVhYzgzXHVjNzQ0IFx1YmEzY1x1YzgwMCBcdWM3NzhcdWMxYzRcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViYjM4XHVjMTFjXHVhYzAwIFx1YzMxM1x1Yzc3OFx1YjJlNFx1YmE3NCBRdWV1ZSBcdWM3OTBcdWI4Y2NcdWFkNmNcdWM4NzBcdWM1ZDAgXHVjMzEzXHVjNWVjXHVjMTFjIEZJRk8gLSBGaXJzdCBJbiBGaXJzdCBPdXQgLSBcdWM1ZDAgXHViNTMwXHViNzdjIFx1Yzc3OFx1YzFjNFx1YWMwMCBcdWI0MThcdWFjOGMgXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWQ1MDRcdWI5YjBcdWQxMzBcdWFlMzAgXHViMGI0XHViZDgwIFx1YzE4Y1x1ZDUwNFx1ZDJiOFx1YzZlOFx1YzViNFx1Yjk3YyBcdWFjMWNcdWJjMWNcdWQ1NThcdWM2MDBcdWIyOTRcdWIzNzAsIFx1Yzc3NCBcdWQ1MDRcdWI5YjBcdWQxMzBcdWFlMzBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4NzBcdWFjNzRcdWM1ZDAgXHViNTMwXHViNzdjIFx1Yzc3OFx1YzFjNFx1Yjk3YyBcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1ZDYwNFx1YzdhYyBRdWV1ZVx1Yzc1OCBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWMxMWNcdWM3NTggJmxzcXVvO1x1YzkxMVx1YzY5NFx1YjNjNCZyc3F1bztcdWI5N2MgXHVkNjU1XHVjNzc4XHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWIwOThcdWJhMzhcdWM5YzAgXHViYjM4XHVjMTFjXHViNGU0IFx1YzkxMSBcdWQ2MDRcdWM3YWMgXHViYjM4XHVjMTFjXHViY2Y0XHViMmU0IFx1YzkxMVx1YzY5NFx1YjNjNFx1YWMwMCBcdWIxOTJcdWM3NDAgXHViYjM4XHVjMTFjXHVhYzAwIFx1ZDU1OFx1YjA5OFx1Yjc3Y1x1YjNjNCBcdWM3ODhcdWIyZTRcdWJhNzQsIFx1Yzc3NCBcdWJiMzhcdWMxMWNcdWI5N2MgXHVjNzc4XHVjMWM0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBRdWV1ZVx1Yzc1OCBcdWFjMDBcdWM3YTUgXHViNGE0XHVjNWQwIFx1YzdhY1x1YmMzMFx1Y2U1OCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQgXHViYzE0XHViODVjIFx1Yzc3OFx1YzFjNFx1Yjk3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBRdWV1ZVx1YzVkMCA0XHVhYzFjXHVjNzU4IFx1YmIzOFx1YzExYyhBIEIgQyBEKVx1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YzkxMVx1YzY5NFx1YjNjNFx1YWMwMCAyIDEgNCAzIFx1Yjc3Y1x1YmE3NCBDXHViOTdjIFx1Yzc3OFx1YzFjNFx1ZDU1OFx1YWNlMCwgXHViMmU0XHVjNzRjXHVjNzNjXHViODVjIERcdWI5N2MgXHVjNzc4XHVjMWM0XHVkNTU4XHVhY2UwIEEsIEJcdWI5N2MgXHVjNzc4XHVjMWM0XHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHViN2VjXHViZDg0XHVjNzc0IFx1ZDU2MCBcdWM3N2NcdWM3NDAsIFx1ZDYwNFx1YzdhYyBRdWV1ZVx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjMTFjXHVjNzU4IFx1YzIxOFx1YzY0MCBcdWM5MTFcdWM2OTRcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNWI0XHViNWE0IFx1ZDU1YyBcdWJiMzhcdWMxMWNcdWFjMDAgXHViYTg3IFx1YmM4OFx1YzlmOFx1Yjg1YyBcdWM3NzhcdWMxYzRcdWI0MThcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViMGI0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM3MDRcdWM3NTggXHVjNjA4XHVjNWQwXHVjMTFjIENcdWJiMzhcdWMxMWNcdWIyOTQgMVx1YmM4OFx1YzlmOFx1Yjg1YywgQVx1YmIzOFx1YzExY1x1YjI5NCAzXHViYzg4XHVjOWY4XHViODVjIFx1Yzc3OFx1YzFjNFx1YjQxOFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIHRlc3QgY2FzZVx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgdGVzdCBjYXNlXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWJiMzhcdWMxMWNcdWM3NTggXHVjMjE4IE4oMTAwXHVjNzc0XHVkNTU4KVx1YzY0MCBcdWJhODcgXHViYzg4XHVjOWY4XHViODVjIFx1Yzc3OFx1YzFjNFx1YjQxOFx1YzVjOFx1YjI5NFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NWMgXHViYjM4XHVjMTFjXHVhYzAwIFx1ZDYwNFx1YzdhYyBRdWV1ZVx1Yzc1OCBcdWM1YjRcdWI1YTQgXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWM1NGNcdWI4MjRcdWM4ZmNcdWIyOTQgTSgwXHVjNzc0XHVjMGMxIE5cdWJiZjhcdWI5Y2MpXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjXHVjOTA0XHVjNWQwIE5cdWFjMWMgXHViYjM4XHVjMTFjXHVjNzU4IFx1YzkxMVx1YzY5NFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsIFx1YzkxMVx1YzY5NFx1YjNjNFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSA5IFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC4gXHVjOTExXHVjNjk0XHViM2M0XHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWMxMWNcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxYyBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNzA0XHVjNzU4IFx1YzYwOFx1YjI5NCBOPTQsIE09MChBXHViYjM4XHVjMTFjXHVhYzAwIFx1YWQ4MVx1YWUwOFx1ZDU1OFx1YjJlNFx1YmE3NCksIFx1YzkxMVx1YzY5NFx1YjNjNFx1YjI5NCAyIDEgNCAzXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgdGVzdCBjYXNlXHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWJiMzhcdWMxMWNcdWFjMDAgXHViYTg3IFx1YmM4OFx1YzlmOFx1Yjg1YyBcdWM3NzhcdWMxYzRcdWI0MThcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE5NjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcmludGVyIFF1ZXVlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgb25seSBwcmludGVyIGluIHRoZSBjb21wdXRlciBzY2llbmNlIHN0dWRlbnRzJnJzcXVvOyB1bmlvbiBpcyBleHBlcmllbmNpbmcgYW4gZXh0cmVtZWx5IGhlYXZ5IHdvcmtsb2FkLiBTb21ldGltZXMgdGhlcmUgYXJlIGEgaHVuZHJlZCBqb2JzIGluIHRoZSBwcmludGVyIHF1ZXVlIGFuZCB5b3UgbWF5IGhhdmUgdG8gd2FpdCBmb3IgaG91cnMgdG8gZ2V0IGEgc2luZ2xlIHBhZ2Ugb2Ygb3V0cHV0LjxcL3A+XHJcblxyXG48cD5CZWNhdXNlIHNvbWUgam9icyBhcmUgbW9yZSBpbXBvcnRhbnQgdGhhbiBvdGhlcnMsIHRoZSBIYWNrZXIgR2VuZXJhbCBoYXMgaW52ZW50ZWQgYW5kIGltcGxlbWVudGVkIGEgc2ltcGxlIHByaW9yaXR5IHN5c3RlbSBmb3IgdGhlIHByaW50IGpvYiBxdWV1ZS4gTm93LCBlYWNoIGpvYiBpcyBhc3NpZ25lZCBhIHByaW9yaXR5IGJldHdlZW4gMSBhbmQgOSAod2l0aCA5IGJlaW5nIHRoZSBoaWdoZXN0IHByaW9yaXR5LCBhbmQgMSBiZWluZyB0aGUgbG93ZXN0KSwgYW5kIHRoZSBwcmludGVyIG9wZXJhdGVzIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjxwPlRoZSBmaXJzdCBqb2IgSiBpbiBxdWV1ZSBpcyB0YWtlbiBmcm9tIHRoZSBxdWV1ZS48YnIgXC8+XHJcbklmIHRoZXJlIGlzIHNvbWUgam9iIGluIHRoZSBxdWV1ZSB3aXRoIGEgaGlnaGVyIHByaW9yaXR5IHRoYW4gam9iIEosIHRoZW4gbW92ZSBKIHRvIHRoZSBlbmQgb2YgdGhlIHF1ZXVlIHdpdGhvdXQgcHJpbnRpbmcgaXQuPGJyIFwvPlxyXG5PdGhlcndpc2UsIHByaW50IGpvYiBKIChhbmQgZG8gbm90IHB1dCBpdCBiYWNrIGluIHRoZSBxdWV1ZSkuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgd2F5LCBhbGwgdGhvc2UgaW1wb3J0YW50IG11ZmZpbiByZWNpcGVzIHRoYXQgdGhlIEhhY2tlciBHZW5lcmFsIGlzIHByaW50aW5nIGdldCBwcmludGVkIHZlcnkgcXVpY2tseS4gT2YgY291cnNlLCB0aG9zZSBhbm5veWluZyB0ZXJtIHBhcGVycyB0aGF0IG90aGVycyBhcmUgcHJpbnRpbmcgbWF5IGhhdmUgdG8gd2FpdCBmb3IgcXVpdGUgc29tZSB0aW1lIHRvIGdldCBwcmludGVkLCBidXQgdGhhdCZyc3F1bztzIGxpZmUuPFwvcD5cclxuXHJcbjxwPllvdXIgcHJvYmxlbSB3aXRoIHRoZSBuZXcgcG9saWN5IGlzIHRoYXQgaXQgaGFzIGJlY29tZSBxdWl0ZSB0cmlja3kgdG8gZGV0ZXJtaW5lIHdoZW4geW91ciBwcmludCBqb2Igd2lsbCBhY3R1YWxseSBiZSBjb21wbGV0ZWQuIFlvdSBkZWNpZGUgdG8gd3JpdGUgYSBwcm9ncmFtIHRvIFx1ZmIwMWd1cmUgdGhpcyBvdXQuIFRoZSBwcm9ncmFtIHdpbGwgYmUgZ2l2ZW4gdGhlIGN1cnJlbnQgcXVldWUgKGFzIGEgbGlzdCBvZiBwcmlvcml0aWVzKSBhcyB3ZWxsIGFzIHRoZSBwb3NpdGlvbiBvZiB5b3VyIGpvYiBpbiB0aGUgcXVldWUsIGFuZCBtdXN0IHRoZW4gY2FsY3VsYXRlIGhvdyBsb25nIGl0IHdpbGwgdGFrZSB1bnRpbCB5b3VyIGpvYiBpcyBwcmludGVkLCBhc3N1bWluZyB0aGF0IG5vIGFkZGl0aW9uYWwgam9icyB3aWxsIGJlIGFkZGVkIHRvIHRoZSBxdWV1ZS4gVG8gc2ltcGxpZnkgbWF0dGVycywgd2UgYXNzdW1lIHRoYXQgcHJpbnRpbmcgYSBqb2IgYWx3YXlzIHRha2VzIGV4YWN0bHkgb25lIG1pbnV0ZSwgYW5kIHRoYXQgYWRkaW5nIGFuZCByZW1vdmluZyBqb2JzIGZyb20gdGhlIHF1ZXVlIGlzIGluc3RhbnRhbmVvdXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbmUgbGluZSB3aXRoIGEgcG9zaXRpdmUgaW50ZWdlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIChhdCBtb3N0IDEwMCkuIFRoZW4gZm9yIGVhY2ggdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzIG4gYW5kIG0sIHdoZXJlIG4gaXMgdGhlIG51bWJlciBvZiBqb2JzIGluIHRoZSBxdWV1ZSAoMSAmbGU7IG4gJmxlOyAxMDApIGFuZCBtIGlzIHRoZSBwb3NpdGlvbiBvZiB5b3VyIGpvYiAoMCAmbGU7IG0gJmxlOyBuJm1pbnVzOzEpLiBUaGUgXHVmYjAxcnN0IHBvc2l0aW9uIGluIHRoZSBxdWV1ZSBpcyBudW1iZXIgMCwgdGhlIHNlY29uZCBpcyBudW1iZXIgMSwgYW5kIHNvIG9uLjxcL2xpPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRobiBpbnRlZ2VycyBpbiB0aGUgcmFuZ2UgMSB0byA5LCBnaXZpbmcgdGhlIHByaW9yaXRpZXMgb2YgdGhlIGpvYnMgaW4gdGhlIHF1ZXVlLiBUaGUgZmlyc3QgaW50ZWdlciBnaXZlcyB0aGUgcHJpb3JpdHkgb2YgdGhlIFx1ZmIwMXJzdCBqb2IsIHRoZSBzZWNvbmQgaW50ZWdlciB0aGUgcHJpb3JpdHkgb2YgdGhlIHNlY29uZCBqb2IsIGFuZCBzbyBvbi48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgb25lIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyOyB0aGUgbnVtYmVyIG9mIG1pbnV0ZXMgdW50aWwgeW91ciBqb2IgaXMgY29tcGxldGVseSBwcmludGVkLCBhc3N1bWluZyB0aGF0IG5vIGFkZGl0aW9uYWwgcHJpbnQgam9icyB3aWxsIGFycml2ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=