시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 168 94 89 60.544%

문제

초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.

하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.

우선 아무나 한 명을 뽑아 줄의 맨 앞에 세운다. 그리고 그 다음부터는 학생이 한 명씩 줄의 맨 뒤에 서면서 다음 과정을 거친다.

  • 자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다.
  • 자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다.

이 과정을 반복하면 결국 오름차순으로 줄을 설 수가 있다.

아이들의 키가 주어지고, 어떤 순서로 아이들이 줄서기를 할 지 주어진다. 위의 방법을 마지막 학생까지 시행하여 줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?

입력

첫 줄에 테스트 케이스의 수 P (1 ≤ P ≤ 1000) 가 주어진다.

각 테스트 케이스는 테스트 케이스 번호 T와 20개의 양의 정수가 공백으로 구분되어 주어진다.

20개의 정수는 줄서기를 할 아이들의 키를 줄서기 차례의 순서대로 밀리미터 단위로 나타낸 것이다.

모든 테스트 케이스는 독립적이다.

출력

각각의 테스트 케이스에 대해 테스트 케이스의 번호와 학생들이 뒤로 물러난 걸음 수의 총합을 공백으로 구분하여 출력한다.

예제 입력 1

4
1 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919
2 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900
3 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 900
4 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 919

예제 출력 1

1 0
2 190
3 19
4 171
W3sicHJvYmxlbV9pZCI6IjEwNDMxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjOTA0XHVjMTM4XHVjNmIwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNkMDhcdWI0ZjFcdWQ1NTlcdWFkNTAgXHVjMTIwXHVjMGRkXHViMmQ4IFx1YWMxNVx1YzBiMFx1Yzc3NFx1YjI5NCBcdWM1NDRcdWM3NzRcdWI0ZTRcdWM3NDQgXHViMzcwXHViOWFjXHVhY2UwIFx1YjJlOFx1Y2NiNFx1Yjg1YyBcdWM1YjRcdWI1YTQgXHVjNzdjXHVjNzQ0IFx1ZDU2MCBcdWI1NGMgXHViZDg4XHVkM2I4XHVkNTY4XHVjNzc0IFx1YzVjNlx1YjNjNFx1Yjg1ZCBcdWMwYzhcdWI4NWMgXHViYzE4XHVjNWQwIFx1YmMzMFx1YzgxNVx1YmMxYlx1Yzc0MCBcdWM1NDRcdWM3NzRcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVkMGE0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWJjODhcdWQ2MzhcdWI5N2MgXHViZDgwXHVjNWVjXHVkNTVjXHViMmU0LiBcdWJjODhcdWQ2MzhcdWI5N2MgXHViZDgwXHVjNWVjXHVkNTYwIFx1YjU1MCBcdWQwYTRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM1NDRcdWM3NzRcdWFjMDAgMVx1YmM4OCwgXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1Yzc3NCAyXHViYzg4LCAuLi4gLCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzU0NFx1Yzc3NFx1YWMwMCAyMFx1YmM4OFx1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1YWMxNVx1YzBiMFx1Yzc3NFx1YjEyNCBcdWJjMTggXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzQwIFx1ZDU2ZFx1YzBjMSAyMFx1YmE4NVx1Yzc3NFx1YmE3MCwgXHViMmU0XHVkNTg5XHVkNzg4XHViM2M0IFx1YWMxOVx1Yzc0MCBcdWQwYTRcdWI5N2MgXHVhYzAwXHVjOWM0IFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWQ1NWMgXHViYTg1XHViM2M0IFx1YzVjNlx1YzViNFx1YzExYyBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjODcwXHVhZTA4IFx1YzljMFx1YjA5OFx1YmE3NCBcdWM1NDRcdWM3NzRcdWI0ZTRcdWM3NDAgXHVjNzkwXHVhZTMwXHViNGU0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM3NzhcdWM5YzBcdWQ1NThcdWFjZTAgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWMxMzhcdWM2YjBcdWJhNzQgXHVjODFjXHViMzAwXHViODVjIFx1YjQxYyBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNzk4IFx1YzExY1x1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWI5ZTRcdWIxNDQgXHVjY2FiIFx1YmE3MFx1Y2U2MFx1YWMwNCBcdWFjMTVcdWMwYjBcdWM3NzRcdWM2NDAgXHVhYzE1XHVjMGIwXHVjNzc0XHViMTI0IFx1YmMxOCBcdWM1NDRcdWM3NzRcdWI0ZTRcdWM3NDAgXHVjNzkwXHVhZTMwXHVhYzAwIFx1ZDBhNCBcdWMyMWNcdWM3M2NcdWI4NWMgXHViYTg3IFx1YmM4OFx1YzlmOFx1Yzc3OFx1YzljMCBcdWM3OTggXHVjNTRjXHVjOWMwIFx1YmFiYlx1ZDU3NCBcdWM1NDRcdWM4ZmMgXHVkNjNjXHViNzgwXHVjMmE0XHViN2ZkXHViMmU0LiBcdWM3OTBcdWFlMzAgXHVjNzA0XHVjZTU4XHViOTdjIFx1Y2MzZVx1YzljMCBcdWJhYmJcdWQ1NThcdWIyOTQgXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzQ0IFx1YzcwNFx1ZDU3NCBcdWFjMTVcdWMwYjBcdWM3NzRcdWIyOTQgXHVkMmI5XHViY2M0XHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWMwZGRcdWFjMDFcdWQ1NzRcdWIwYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YzEyMCBcdWM1NDRcdWJiMzRcdWIwOTggXHVkNTVjIFx1YmE4NVx1Yzc0NCBcdWJmNTFcdWM1NDQgXHVjOTA0XHVjNzU4IFx1YjllOCBcdWM1NWVcdWM1ZDAgXHVjMTM4XHVjNmI0XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YmQ4MFx1ZDEzMFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVkNTVjIFx1YmE4NVx1YzUyOSBcdWM5MDRcdWM3NTggXHViOWU4IFx1YjRhNFx1YzVkMCBcdWMxMWNcdWJhNzRcdWMxMWMgXHViMmU0XHVjNzRjIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWFjNzBcdWNlNWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjNzkwXHVhZTMwIFx1YzU1ZVx1YzVkMCBcdWM3OTBcdWFlMzBcdWJjZjRcdWIyZTQgXHVkMGE0XHVhYzAwIFx1ZDA3MCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0IFx1YWRmOFx1YjBlNSBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwIFx1YzExY1x1YWNlMCBcdWNjMjhcdWI4NDBcdWFjMDAgXHViMDVkXHViMDljXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3OTBcdWFlMzAgXHVjNTVlXHVjNWQwIFx1Yzc5MFx1YWUzMFx1YmNmNFx1YjJlNCBcdWQwYTRcdWFjMDAgXHVkMDcwIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWQ1NWMgXHViYTg1IFx1Yzc3NFx1YzBjMSBcdWM3ODhcdWIyZTRcdWJhNzQgXHVhZGY4XHVjOTExIFx1YWMwMFx1YzdhNSBcdWM1NWVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDU1OVx1YzBkZChBKVx1Yzc1OCBcdWJjMTRcdWI4NWMgXHVjNTVlXHVjNWQwIFx1YzEyMFx1YjJlNC4gXHVjNzc0XHViNTRjLCBBXHViZDgwXHVkMTMwIFx1YWRmOCBcdWI0YTRcdWM3NTggXHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWFjZjVcdWFjMDRcdWM3NDQgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NWMgXHViYzFjXHVjNTI5IFx1YjRhNFx1Yjg1YyBcdWJiM2NcdWI3ZWNcdWMxMWNcdWFjOGMgXHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc3NCBcdWFjZmNcdWM4MTVcdWM3NDQgXHViYzE4XHViY2Y1XHVkNTU4XHViYTc0IFx1YWNiMFx1YWQ2ZCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjOTA0XHVjNzQ0IFx1YzEyNCBcdWMyMThcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWM3NzRcdWI0ZTRcdWM3NTggXHVkMGE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwgXHVjNWI0XHViNWE0IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWM1NDRcdWM3NzRcdWI0ZTRcdWM3NzQgXHVjOTA0XHVjMTFjXHVhZTMwXHViOTdjIFx1ZDU2MCBcdWM5YzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3MDRcdWM3NTggXHViYzI5XHViYzk1XHVjNzQ0IFx1YjljOFx1YzljMFx1YjljOSBcdWQ1NTlcdWMwZGRcdWFlNGNcdWM5YzAgXHVjMmRjXHVkNTg5XHVkNTU4XHVjNWVjIFx1YzkwNFx1YzExY1x1YWUzMFx1YWMwMCBcdWIwNWRcdWIwYWNcdWM3NDQgXHViNTRjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWNkMWQgXHViYTg3IFx1YmM4OCBcdWI0YTRcdWI4NWMgXHViYjNjXHViN2VjXHVjMTFjXHVhYzhjIFx1YjQyMFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggUCAoMSAmbGU7IFAgJmxlOyAxMDAwKSBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOCBUXHVjNjQwIDIwXHVhYzFjXHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjIwXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWM5MDRcdWMxMWNcdWFlMzBcdWI5N2MgXHVkNTYwIFx1YzU0NFx1Yzc3NFx1YjRlNFx1Yzc1OCBcdWQwYTRcdWI5N2MgXHVjOTA0XHVjMTFjXHVhZTMwIFx1Y2MyOFx1Yjg0MFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViYzAwXHViOWFjXHViYmY4XHVkMTMwIFx1YjJlOFx1YzcwNFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWIzYzVcdWI5YmRcdWM4MDFcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViYzg4XHVkNjM4XHVjNjQwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWI0YTRcdWI4NWMgXHViYjNjXHViN2VjXHViMDljIFx1YWM3OFx1Yzc0YyBcdWMyMThcdWM3NTggXHVjZDFkXHVkNTY5XHVjNzQ0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNDMxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSGVpZ2h0IE9yZGVyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5NcnMuIENoYW1iZXJzIGFsd2F5cyBoYXMgaGVyIGNsYXNzIGxpbmUgdXAgaW4gaGVpZ2h0IG9yZGVyIChzaG9ydGVzdCBhdCB0aGUgZnJvbnQgb2YgdGhlIGxpbmUpLiBFdmVyeSBTZXB0ZW1iZXIgYSBuZXcgY2xhc3Mgb2YgZXhhY3RseSAyMCAzcmQgZ3JhZGVycyBhcnJpdmUsIGFsbCBvZiBkaWZmZXJlbnQgaGVpZ2h0LiBGb3IgdGhlIGZpcnN0IGZldyBkYXlzIGl0IHRha2VzIGEgbG9uZyB0aW1lIHRvIGdldCB0aGUga2lkcyBpbiBoZWlnaHQgb3JkZXIsIHNpbmNlIG5vIG9uZSBrbm93cyB3aGVyZSB0aGV5IHNob3VsZCBiZSBpbiB0aGUgbGluZS4gTmVlZGxlc3MgdG8gc2F5LCB0aGVyZSBpcyBxdWl0ZSBhIGJpdCBvZiBqb2NrZXlpbmcgYXJvdW5kLiBUaGlzIHllYXIgTXJzLiBDaGFtYmVycyBkZWNpZGVkIHRvIHRyeSBhIG5ldyBtZXRob2QgdG8gbWluaW1pemUgdGhpcyBvcmRlcmluZyBjaGFvcy4gT25lIHN0dWRlbnQgd291bGQgYmUgc2VsZWN0ZWQgdG8gYmUgdGhlIGZpcnN0IHBlcnNvbiBpbiBsaW5lLiBUaGVuLCBhbm90aGVyIHN0dWRlbnQgaXMgc2VsZWN0ZWQgYW5kIHdvdWxkIGZpbmQgdGhlIGZpcnN0IHBlcnNvbiBpbiB0aGUgbGluZSB0aGF0IGlzIHRhbGxlciB0aGFuIGhpbSwgYW5kIHN0YW5kIGluIGZyb250IG9mIHRoYXQgcGVyc29uLCB0aGVyZWJ5IGNhdXNpbmcgYWxsIHRoZSBzdHVkZW50cyBiZWhpbmQgaGltIHRvIHN0ZXAgYmFjayB0byBtYWtlIHJvb20uIElmIHRoZXJlIGlzIG5vIHN0dWRlbnQgdGhhdCBpcyB0YWxsZXIsIHRoZW4gaGUgd291bGQgc3RhbmQgYXQgdGhlIGVuZCBvZiB0aGUgbGluZS4gVGhpcyBwcm9jZXNzIGNvbnRpbnVlcywgb25lIHN0dWRlbnQgYXQtYS10aW1lLCB1bnRpbCBhbGwgdGhlIHN0dWRlbnRzIGFyZSBpbiBsaW5lLCBhdCB3aGljaCBwb2ludCB0aGUgc3R1ZGVudHMgd2lsbCBiZSBsaW5lZCB1cCBpbiBoZWlnaHQgb3JkZXIuPFwvcD5cclxuXHJcbjxwPkZvciB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIHRvdGFsIG51bWJlciBvZiBzdGVwcyB0YWtlbiBiYWNrIGR1cmluZyB0aGUgb3JkZXJpbmcgcHJvY2VzcyBmb3IgYSBnaXZlbiBjbGFzcyBvZiBzdHVkZW50cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LiBFYWNoIGRhdGEgc2V0IHNob3VsZCBiZSBwcm9jZXNzZWQgaWRlbnRpY2FsbHkgYW5kIGluZGVwZW5kZW50bHkuPFwvcD5cclxuXHJcbjxwPkVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgbGluZSBvZiBpbnB1dC4gSXQgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciwgSywgZm9sbG93ZWQgYnkgMjAgbm9uLW5lZ2F0aXZlIHVuaXF1ZSBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuIFRoZSAyMCBpbnRlZ2VycyByZXByZXNlbnQgdGhlIGhlaWdodCAoaW4gbWlsbGltZXRlcnMpIG9mIGVhY2ggc3R1ZGVudCBpbiB0aGUgY2xhc3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQgdGhlcmUgaXMgb25lIGxpbmUgb2Ygb3V0cHV0LiBUaGUgc2luZ2xlIG91dHB1dCBsaW5lIGNvbnNpc3RzIG9mIHRoZSBkYXRhIHNldCBudW1iZXIsIEssIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlIGZvbGxvd2VkIGJ5IHRvdGFsIG51bWJlciBvZiBzdGVwcyB0YWtlbiBiYWNrLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==