시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 164 91 86 60.140%

문제

초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 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+XHVjNzkwXHVhZTMwIFx1YzU1ZVx1YzVkMCBcdWM3OTBcdWFlMzBcdWJjZjRcdWIyZTQgXHVkMGE0XHVhYzAwIFx1ZDA3MCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjNWM2XHViMmU0XHViYTc0IFx1YWRmOFx1YjBlNSBcdWFkZjggXHVjNzkwXHViOWFjXHVjNWQwIFx1YzExY1x1YWNlMCBcdWNjMjhcdWI4NDBcdWFjMDAgXHViMDVkXHViMDljXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3OTBcdWFlMzAgXHVjNTVlXHVjNWQwIFx1Yzc5MFx1YWUzMFx1YmNmNFx1YjJlNCBcdWQwYTRcdWFjMDAgXHVkMDcwIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWQ1NWMgXHViYTg1IFx1Yzc3NFx1YzBjMSBcdWM3ODhcdWIyZTRcdWJhNzQgXHVhZGY4XHVjOTExIFx1YWMwMFx1YzdhNSBcdWM1NWVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDU1OVx1YzBkZChBKVx1Yzc1OCBcdWJjMTRcdWI4NWMgXHVjNTVlXHVjNWQwIFx1YzEyMFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgQVx1YmQ4MFx1ZDEzMCBcdWFkZjggXHViNGE0XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVhY2Y1XHVhYzA0XHVjNzQ0IFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTVjIFx1YmMxY1x1YzUyOSBcdWI0YTRcdWI4NWMgXHViYjNjXHViN2VjXHVjMTFjXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NzQgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YmMxOFx1YmNmNVx1ZDU1OFx1YmE3NCBcdWFjYjBcdWFkNmQgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YzkwNFx1Yzc0NCBcdWMxMjQgXHVjMjE4XHVhYzAwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHVjNzc0XHViNGU0XHVjNzU4IFx1ZDBhNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YzViNFx1YjVhNCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjNTQ0XHVjNzc0XHViNGU0XHVjNzc0IFx1YzkwNFx1YzExY1x1YWUzMFx1Yjk3YyBcdWQ1NjAgXHVjOWMwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzA0XHVjNzU4IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVkNTU5XHVjMGRkXHVhZTRjXHVjOWMwIFx1YzJkY1x1ZDU4OVx1ZDU1OFx1YzVlYyBcdWM5MDRcdWMxMWNcdWFlMzBcdWFjMDAgXHViMDVkXHViMGFjXHVjNzQ0IFx1YjU0YyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHVjZDFkIFx1YmE4NyBcdWJjODggXHViNGE0XHViODVjIFx1YmIzY1x1YjdlY1x1YzExY1x1YWM4YyBcdWI0MjBcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4IFAgKDEgJmxlOyBQICZsZTsgMTAwMCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWJjODhcdWQ2MzggVFx1YzY0MCAyMFx1YWMxY1x1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD4yMFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWIyOTQgXHVjOTA0XHVjMTFjXHVhZTMwXHViOTdjIFx1ZDU2MCBcdWM1NDRcdWM3NzRcdWI0ZTRcdWM3NTggXHVkMGE0XHViOTdjIFx1YzkwNFx1YzExY1x1YWUzMCBcdWNjMjhcdWI4NDBcdWM3NTggXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YmMwMFx1YjlhY1x1YmJmOFx1ZDEzMCBcdWIyZThcdWM3MDRcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViM2M1XHViOWJkXHVjODAxXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHViNGE0XHViODVjIFx1YmIzY1x1YjdlY1x1YjA5YyBcdWFjNzhcdWM3NGMgXHVjMjE4XHVjNzU4IFx1Y2QxZFx1ZDU2OVx1Yzc0NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDQzMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhlaWdodCBPcmRlcmluZyIsImRlc2NyaXB0aW9uIjoiPHA+TXJzLiBDaGFtYmVycyBhbHdheXMgaGFzIGhlciBjbGFzcyBsaW5lIHVwIGluIGhlaWdodCBvcmRlciAoc2hvcnRlc3QgYXQgdGhlIGZyb250IG9mIHRoZSBsaW5lKS4gRXZlcnkgU2VwdGVtYmVyIGEgbmV3IGNsYXNzIG9mIGV4YWN0bHkgMjAgM3JkIGdyYWRlcnMgYXJyaXZlLCBhbGwgb2YgZGlmZmVyZW50IGhlaWdodC4gRm9yIHRoZSBmaXJzdCBmZXcgZGF5cyBpdCB0YWtlcyBhIGxvbmcgdGltZSB0byBnZXQgdGhlIGtpZHMgaW4gaGVpZ2h0IG9yZGVyLCBzaW5jZSBubyBvbmUga25vd3Mgd2hlcmUgdGhleSBzaG91bGQgYmUgaW4gdGhlIGxpbmUuIE5lZWRsZXNzIHRvIHNheSwgdGhlcmUgaXMgcXVpdGUgYSBiaXQgb2Ygam9ja2V5aW5nIGFyb3VuZC4gVGhpcyB5ZWFyIE1ycy4gQ2hhbWJlcnMgZGVjaWRlZCB0byB0cnkgYSBuZXcgbWV0aG9kIHRvIG1pbmltaXplIHRoaXMgb3JkZXJpbmcgY2hhb3MuIE9uZSBzdHVkZW50IHdvdWxkIGJlIHNlbGVjdGVkIHRvIGJlIHRoZSBmaXJzdCBwZXJzb24gaW4gbGluZS4gVGhlbiwgYW5vdGhlciBzdHVkZW50IGlzIHNlbGVjdGVkIGFuZCB3b3VsZCBmaW5kIHRoZSBmaXJzdCBwZXJzb24gaW4gdGhlIGxpbmUgdGhhdCBpcyB0YWxsZXIgdGhhbiBoaW0sIGFuZCBzdGFuZCBpbiBmcm9udCBvZiB0aGF0IHBlcnNvbiwgdGhlcmVieSBjYXVzaW5nIGFsbCB0aGUgc3R1ZGVudHMgYmVoaW5kIGhpbSB0byBzdGVwIGJhY2sgdG8gbWFrZSByb29tLiBJZiB0aGVyZSBpcyBubyBzdHVkZW50IHRoYXQgaXMgdGFsbGVyLCB0aGVuIGhlIHdvdWxkIHN0YW5kIGF0IHRoZSBlbmQgb2YgdGhlIGxpbmUuIFRoaXMgcHJvY2VzcyBjb250aW51ZXMsIG9uZSBzdHVkZW50IGF0LWEtdGltZSwgdW50aWwgYWxsIHRoZSBzdHVkZW50cyBhcmUgaW4gbGluZSwgYXQgd2hpY2ggcG9pbnQgdGhlIHN0dWRlbnRzIHdpbGwgYmUgbGluZWQgdXAgaW4gaGVpZ2h0IG9yZGVyLjxcL3A+XHJcblxyXG48cD5Gb3IgdGhpcyBwcm9ibGVtLCB5b3Ugd2lsbCB3cml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSB0b3RhbCBudW1iZXIgb2Ygc3RlcHMgdGFrZW4gYmFjayBkdXJpbmcgdGhlIG9yZGVyaW5nIHByb2Nlc3MgZm9yIGEgZ2l2ZW4gY2xhc3Mgb2Ygc3R1ZGVudHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbnVtYmVyIG9mIGRhdGEgc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhIHNldCBzaG91bGQgYmUgcHJvY2Vzc2VkIGlkZW50aWNhbGx5IGFuZCBpbmRlcGVuZGVudGx5LjxcL3A+XHJcblxyXG48cD5FYWNoIGRhdGEgc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgb2YgaW5wdXQuIEl0IGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIsIEssIGZvbGxvd2VkIGJ5IDIwIG5vbi1uZWdhdGl2ZSB1bmlxdWUgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGUgMjAgaW50ZWdlcnMgcmVwcmVzZW50IHRoZSBoZWlnaHQgKGluIG1pbGxpbWV0ZXJzKSBvZiBlYWNoIHN0dWRlbnQgaW4gdGhlIGNsYXNzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIG9uZSBsaW5lIG9mIG91dHB1dC4gVGhlIHNpbmdsZSBvdXRwdXQgbGluZSBjb25zaXN0cyBvZiB0aGUgZGF0YSBzZXQgbnVtYmVyLCBLLCBmb2xsb3dlZCBieSBhIHNpbmdsZSBzcGFjZSBmb2xsb3dlZCBieSB0b3RhbCBudW1iZXIgb2Ygc3RlcHMgdGFrZW4gYmFjay48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=