시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 66 23 22 50.000%

문제

선종이는 최근에 배열을 정렬하는 새로운 알고리즘을 이길흥 교수님의 강의에서 배웠습니다. 그 알고리즘은 배열의 숫자들을 반복적으로 삭제, 삽입을 수행하여 배열을 정렬합니다. 선종이는 이 정렬 알고리즘을 삭삽 정렬이라 이름 붙였습니다. 삭삽 정렬은 다음과 같은 과정을 수행합니다.

  1. 배열의 요소 하나를 선택합니다.
  2. 배열에서 해당 요소를 삭제합니다.
  3. 해당 요소를 배열의 맨 뒤에 삽입합니다.

선종이는 호기심이 많은 학생이기 때문에, 삭삽 정렬을 수행하여 배열을 정렬 할 때 가장 적게 위와 같은 삭삽 과정이 얼마나 수행되는지 알아보고 싶어졌습니다.

입력

입력의 첫 번째 줄에는 테스트케이스를 나타내는 P(1 ≤ P ≤ 100)가 주어집니다. 이후 이어지는 행에서 각각 테스트케이스에 해당하는 데이터 세트가 주어집니다.

각각 데이터 세트는 조건에서 주어진 대로 삭삽 정렬을 수행해야하며, 독립적으로 처리되어야 합니다. 각 데이터 세트는 최소 두 행 이상이 주어집니다.

첫 번째 행에서 데이터 세트의 번호인 K와 공백 이후 정렬 할 배열의 길이인 N(1 ≤ N ≤ 1000)이 주어집니다.

그 이후 행에서 정렬 할 배열을 구성하는 N개의 양의 정수가 주어지는데, 마지막 행을 제외한 모든 행에서 10개로 이루어진 109 보다 작은 숫자들이 주어집니다. (마지막 행은 10개 보다 적은 숫자들이 주어집니다.)

주어지는 숫자들은 동일한 숫자가 여러 번 주어질 수 있습니다.

출력

각각의 데이터 세트의 번호를 나타내는 K와 공백 이후 최소 삭삽 정렬 과정 수행 횟수를 한 행으로 출력합니다.

예제 입력 1

3
1 3
1 3 2
2 6
1 5 2 4 3 6
3 23
67890 56312 999999999 12345 23456 38927 45632 100345 98765 23456
87654 43278 23456 117654 321899 25432 54326 217435 26845 31782
33456 41234 56213

예제 출력 1

1 1
2 3
3 15

힌트

예제 입력의 첫 번째 데이터 세트인,

1 3

1 3 2

는 다음과 같은 삭삽 정렬 과정을 거칩니다.

3을 선택하여 삭제하고, 배열의 맨 뒤에 삽입하여

1 2 3

으로 1번의 삭삽 정렬 과정을 수행하여 정렬을 종료하여

1 1

을 출력합니다.

W3sicHJvYmxlbV9pZCI6IjEzODg0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMGFkXHVjMGJkIFx1YzgxNVx1YjgyYyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMTIwXHVjODg1XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YWRmY1x1YzVkMCBcdWJjMzBcdWM1ZjRcdWM3NDQgXHVjODE1XHViODJjXHVkNTU4XHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDQgXHVjNzc0XHVhZTM4XHVkNzY1IFx1YWQ1MFx1YzIxOFx1YjJkOFx1Yzc1OCBcdWFjMTVcdWM3NThcdWM1ZDBcdWMxMWMgXHViYzMwXHVjNmUwXHVjMmI1XHViMmM4XHViMmU0LiBcdWFkZjggXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQwIFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI0ZTRcdWM3NDQgXHViYzE4XHViY2Y1XHVjODAxXHVjNzNjXHViODVjIFx1YzBhZFx1YzgxYywgXHVjMGJkXHVjNzg1XHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YzVlYyBcdWJjMzBcdWM1ZjRcdWM3NDQgXHVjODE1XHViODJjXHVkNTY5XHViMmM4XHViMmU0LiBcdWMxMjBcdWM4ODVcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YzgxNVx1YjgyYyBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDQgXHVjMGFkXHVjMGJkIFx1YzgxNVx1YjgyY1x1Yzc3NFx1Yjc3YyBcdWM3NzRcdWI5ODQgXHViZDk5XHVjNjAwXHVjMmI1XHViMmM4XHViMmU0LiBcdWMwYWRcdWMwYmQgXHVjODE1XHViODJjXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJjMzBcdWM1ZjRcdWM3NTggXHVjNjk0XHVjMThjIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmMzMFx1YzVmNFx1YzVkMFx1YzExYyBcdWQ1NzRcdWIyZjkgXHVjNjk0XHVjMThjXHViOTdjIFx1YzBhZFx1YzgxY1x1ZDU2OVx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVkNTc0XHViMmY5IFx1YzY5NFx1YzE4Y1x1Yjk3YyBcdWJjMzBcdWM1ZjRcdWM3NTggXHViOWU4IFx1YjRhNFx1YzVkMCBcdWMwYmRcdWM3ODVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjMTIwXHVjODg1XHVjNzc0XHViMjk0IFx1ZDYzOFx1YWUzMFx1YzJlY1x1Yzc3NCBcdWI5Y2VcdWM3NDAgXHVkNTU5XHVjMGRkXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMGFkXHVjMGJkIFx1YzgxNVx1YjgyY1x1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NThcdWM1ZWMgXHViYzMwXHVjNWY0XHVjNzQ0IFx1YzgxNVx1YjgyYyBcdWQ1NjAgXHViNTRjIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMwYWRcdWMwYmQgXHVhY2ZjXHVjODE1XHVjNzc0IFx1YzViY1x1YjljOFx1YjA5OCBcdWMyMThcdWQ1ODlcdWI0MThcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViY2Y0XHVhY2UwIFx1YzJmNlx1YzViNFx1Yzg0Y1x1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFAoMSAmbGU7IFAgJmxlOyAxMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHVjNzc0XHVkNmM0IFx1Yzc3NFx1YzViNFx1YzljMFx1YjI5NCBcdWQ1ODlcdWM1ZDBcdWMxMWMgXHVhYzAxXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMVx1YWMwMSBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4XHViMjk0IFx1Yzg3MFx1YWM3NFx1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViMzAwXHViODVjIFx1YzBhZFx1YzBiZCBcdWM4MTVcdWI4MmNcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTc0XHVjNTdjXHVkNTU4XHViYTcwLCBcdWIzYzVcdWI5YmRcdWM4MDFcdWM3M2NcdWI4NWMgXHVjYzk4XHViOWFjXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU2OVx1YjJjOFx1YjJlNC4gXHVhYzAxIFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjhcdWIyOTQgXHVjZDVjXHVjMThjIFx1YjQ1MCBcdWQ1ODkgXHVjNzc0XHVjMGMxXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQ1ODlcdWM1ZDBcdWMxMWMgXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWM3NzggS1x1YzY0MCBcdWFjZjVcdWJjMzEgXHVjNzc0XHVkNmM0IFx1YzgxNVx1YjgyYyBcdWQ1NjAgXHViYzMwXHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3OCBOKDEgJmxlOyBOICZsZTsgMTAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFkZjggXHVjNzc0XHVkNmM0IFx1ZDU4OVx1YzVkMFx1YzExYyBcdWM4MTVcdWI4MmMgXHVkNTYwIFx1YmMzMFx1YzVmNFx1Yzc0NCBcdWFkNmNcdWMxMzFcdWQ1NThcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NFx1YjM3MCwgXHViOWM4XHVjOWMwXHViOWM5IFx1ZDU4OVx1Yzc0NCBcdWM4MWNcdWM2NzhcdWQ1NWMgXHViYWE4XHViNGUwIFx1ZDU4OVx1YzVkMFx1YzExYyAxMFx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgMTA8c3VwPjkgPFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjMjJiXHVjNzkwXHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gKFx1YjljOFx1YzljMFx1YjljOSBcdWQ1ODlcdWM3NDAgMTBcdWFjMWMgXHViY2Y0XHViMmU0IFx1YzgwMVx1Yzc0MCBcdWMyMmJcdWM3OTBcdWI0ZTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YzIyYlx1Yzc5MFx1YjRlNFx1Yzc0MCBcdWIzZDlcdWM3N2NcdWQ1NWMgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YzVlY1x1YjdlYyBcdWJjODggXHVjOGZjXHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjhcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBLXHVjNjQwIFx1YWNmNVx1YmMzMSBcdWM3NzRcdWQ2YzQgXHVjZDVjXHVjMThjIFx1YzBhZFx1YzBiZCBcdWM4MTVcdWI4MmMgXHVhY2ZjXHVjODE1IFx1YzIxOFx1ZDU4OSBcdWQ2OWZcdWMyMThcdWI5N2MgXHVkNTVjIFx1ZDU4OVx1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4XHVjNzc4LDxcL3A+XHJcblxyXG48cD4xIDM8XC9wPlxyXG5cclxuPHA+MSAzIDI8XC9wPlxyXG5cclxuPHA+XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMGFkXHVjMGJkIFx1YzgxNVx1YjgyYyBcdWFjZmNcdWM4MTVcdWM3NDQgXHVhYzcwXHVjZTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD4zXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YzVlYyBcdWMwYWRcdWM4MWNcdWQ1NThcdWFjZTAsIFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWI5ZTggXHViNGE0XHVjNWQwIFx1YzBiZFx1Yzc4NVx1ZDU1OFx1YzVlYzxcL3A+XHJcblxyXG48cD4xIDIgMzxcL3A+XHJcblxyXG48cD48c3BhbiBzdHlsZT1cImZvbnQtZmFtaWx5OkFyaWFsLCZxdW90O0hlbHZldGljYSBOZXVlJnF1b3Q7LEhlbHZldGljYSxUYWhvbWEsc2Fucy1zZXJpZlwiPlx1YzczY1x1Yjg1YyAxXHViYzg4XHVjNzU4IFx1YzBhZFx1YzBiZCBcdWM4MTVcdWI4MmMgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YzVlYyBcdWM4MTVcdWI4MmNcdWM3NDQgXHVjODg1XHViOGNjXHVkNTU4XHVjNWVjPFwvc3Bhbj48XC9wPlxyXG5cclxuPHA+MSAxPFwvcD5cclxuXHJcbjxwPjxzcGFuIHN0eWxlPVwiZm9udC1mYW1pbHk6QXJpYWwsJnF1b3Q7SGVsdmV0aWNhIE5ldWUmcXVvdDssSGVsdmV0aWNhLFRhaG9tYSxzYW5zLXNlcmlmXCI+XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU2OVx1YjJjOFx1YjJlNC48XC9zcGFuPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTM4ODQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEQS1Tb3J0IiwiZGVzY3JpcHRpb24iOiI8cD5Zb3UgcmVjZW50bHkgbGVhcm5lZCBhIG5ldyB3YXkgdG8gc29ydCBhbiBhcnJheSBvZiBudW1iZXJzIGluIHlvdXIgYWxnb3JpdGhtcyBjb3Vyc2UuIFRoZSBhbGdvcml0aG0gc29ydHMgYW4gYXJyYXkgb2YgbnVtYmVycyBieSByZXBlYXRlZGx5IHBlcmZvcm1pbmcgdGhlIERlbGV0ZS1hbmQtQXBwZW5kIG9wZXJhdGlvbi4gVGhlIERlbGV0ZWFuZC1BcHBlbmQgb3BlcmF0aW9uIGNvbnNpc3RzIG9mIHRocmVlIHN0ZXBzOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkNob29zZSBhbiBlbGVtZW50IGZyb20gdGhlIGFycmF5LjxcL2xpPlxyXG5cdDxsaT5EZWxldGUgdGhlIGNob3NlbiBlbGVtZW50IGZyb20gdGhlIGFycmF5LjxcL2xpPlxyXG5cdDxsaT5BcHBlbmQgdGhlIGNob3NlbiBlbGVtZW50IHRvIHRoZSBlbmQgb2YgdGhlIGFycmF5LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkJlaW5nIGEgY3VyaW91cyBzdHVkZW50LCB5b3Ugd29uZGVyIHdoYXQgaXMgdGhlIG1pbmltdW0gbnVtYmVyIG9mIERlbGV0ZS1hbmQtQXBwZW5kIG9wZXJhdGlvbnMgcmVxdWlyZWQgdG8gc29ydCBhIGdpdmVuIGFycmF5LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgZGVjaW1hbCBpbnRlZ2VyIFAsICgxICZsZTsgUCAmbGU7IDEwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2YgZGF0YSBzZXRzIHRoYXQgZm9sbG93LjxcL3A+XHJcblxyXG48cD5FYWNoIGRhdGEgc2V0IHNob3VsZCBiZSBwcm9jZXNzZWQgaWRlbnRpY2FsbHkgYW5kIGluZGVwZW5kZW50bHkuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgdHdvIG9yIG1vcmUgbGluZXMgb2YgaW5wdXQuIFRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIHRoZSBkYXRhIHNldCBudW1iZXIsIEssIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlLCBmb2xsb3dlZCBieSBhbiBpbnRlZ2VyIE4sICgxICZsZTsgTiAmbGU7IDEwMDApLCB3aGljaCBpcyB0aGUgbGVuZ3RoIG9mIHRoZSBhcnJheSB0byBzb3J0LiBUaGUgcmVtYWluaW5nIGxpbmVzIGluIHRoZSBkYXRhc2V0IGNvbnRhaW5zIE4gcG9zaXRpdmUgaW50ZWdlcnMgdGhhdCBjb21wcmlzZSB0aGUgYXJyYXkgdG8gYmUgc29ydGVkLCAxMCB2YWx1ZXMgcGVyIGxpbmUsIGV4Y2VwdCBmb3IgdGhlIGxhc3QgbGluZSB3aGljaCBtYXkgaGF2ZSBsZXNzIHRoYW4gMTAgdmFsdWVzLiBBbGwgdGhlIGFycmF5IGVsZW1lbnRzIGFyZSBubyBsYXJnZXIgdGhhbiAxMDxzdXA+OTxcL3N1cD4uIFRoZSBzYW1lIHZhbHVlIG1heSBhcHBlYXIgbW9yZSB0aGFuIG9uY2UgaW4gdGhlIGFycmF5IHRvIGJlIHNvcnRlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCB0aGVyZSBpcyBvbmUgbGluZSBvZiBvdXRwdXQuIFRoZSBzaW5nbGUgb3V0cHV0IGxpbmUgY29uc2lzdHMgb2YgdGhlIGRhdGEgc2V0IG51bWJlciwgSywgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UgZm9sbG93ZWQgYnkgYW4gaW50ZWdlciB3aGljaCBpcyB0aGUgbWluaW11bSBudW1iZXIgb2YgRGVsZXRlLWFuZEFwcGVuZCBvcGVyYXRpb25zIHJlcXVpcmVkIHRvIHNvcnQgdGhlIGFycmF5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==