시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 45 13 13 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+XHVjMTIwXHVjODg1XHVjNzc0XHViMjk0IFx1ZDYzOFx1YWUzMFx1YzJlY1x1Yzc3NCBcdWI5Y2VcdWM3NDAgXHVkNTU5XHVjMGRkXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjMGFkXHVjMGJkIFx1YzgxNVx1YjgyY1x1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NThcdWM1ZWMgXHViYzMwXHVjNWY0XHVjNzQ0IFx1YzgxNVx1YjgyYyBcdWQ1NjAgXHViNTRjIFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMwYWRcdWMwYmQgXHVhY2ZjXHVjODE1XHVjNzc0IFx1YzViY1x1YjljOFx1YjA5OCBcdWMyMThcdWQ1ODlcdWI0MThcdWIyOTRcdWM5YzAgXHVjNTRjXHVjNTQ0XHViY2Y0XHVhY2UwIFx1YzJmNlx1YzViNFx1Yzg0Y1x1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgUCgxICZsZTsgUCAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiBcdWM3NzRcdWQ2YzQgXHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IFx1ZDU4OVx1YzVkMFx1YzExYyBcdWFjMDFcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVjMTM4XHVkMmI4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxXHVhYzAxIFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjhcdWIyOTQgXHVjODcwXHVhYzc0XHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWIzMDBcdWI4NWMgXHVjMGFkXHVjMGJkIFx1YzgxNVx1YjgyY1x1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NzRcdWM1N2NcdWQ1NThcdWJhNzAsIFx1YjNjNVx1YjliZFx1YzgwMVx1YzczY1x1Yjg1YyBcdWNjOThcdWI5YWNcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTY5XHViMmM4XHViMmU0LiBcdWFjMDEgXHViMzcwXHVjNzc0XHVkMTMwIFx1YzEzOFx1ZDJiOFx1YjI5NCBcdWNkNWNcdWMxOGMgXHViNDUwIFx1ZDU4OSBcdWM3NzRcdWMwYzFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVkNTg5XHVjNWQwXHVjMTFjIFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjhcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc4IEtcdWM2NDAgXHVhY2Y1XHViYzMxIFx1Yzc3NFx1ZDZjNCBcdWM4MTVcdWI4MmMgXHVkNTYwIFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWM3NzggTigxICZsZTsgTiAmbGU7IDEwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGY4IFx1Yzc3NFx1ZDZjNCBcdWQ1ODlcdWM1ZDBcdWMxMWMgXHVjODE1XHViODJjIFx1ZDU2MCBcdWJjMzBcdWM1ZjRcdWM3NDQgXHVhZDZjXHVjMTMxXHVkNTU4XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTRcdWIzNzAsIFx1YjljOFx1YzljMFx1YjljOSBcdWQ1ODlcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWQ1ODlcdWM1ZDBcdWMxMWMgMTBcdWFjMWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IDEwPHN1cD45IDxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YzIyYlx1Yzc5MFx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIChcdWI5YzhcdWM5YzBcdWI5YzkgXHVkNTg5XHVjNzQwIDEwXHVhYzFjIFx1YmNmNFx1YjJlNCBcdWM4MDFcdWM3NDAgXHVjMjJiXHVjNzkwXHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWMyMmJcdWM3OTBcdWI0ZTRcdWM3NDAgXHViM2Q5XHVjNzdjXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM1ZWNcdWI3ZWNcdWJjODggXHVjOGZjXHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjhcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBLXHVjNjQwIFx1YWNmNVx1YmMzMSBcdWM3NzRcdWQ2YzQgXHVjZDVjXHVjMThjIFx1YzBhZFx1YzBiZCBcdWM4MTVcdWI4MmMgXHVhY2ZjXHVjODE1IFx1YzIxOFx1ZDU4OSBcdWQ2OWZcdWMyMThcdWI5N2MgXHVkNTVjIFx1ZDU4OVx1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHViYzg4XHVjOWY4IFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxMzhcdWQyYjhcdWM3NzgsPFwvcD5cclxuXHJcbjxwPjEgMzxcL3A+XHJcblxyXG48cD4xIDMgMjxcL3A+XHJcblxyXG48cD5cdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMwYWRcdWMwYmQgXHVjODE1XHViODJjIFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWFjNzBcdWNlNjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjNcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHVjNWVjIFx1YzBhZFx1YzgxY1x1ZDU1OFx1YWNlMCwgXHViYzMwXHVjNWY0XHVjNzU4IFx1YjllOCBcdWI0YTRcdWM1ZDAgXHVjMGJkXHVjNzg1XHVkNTU4XHVjNWVjPFwvcD5cclxuXHJcbjxwPjEgMiAzPFwvcD5cclxuXHJcbjxwPjxzcGFuIHN0eWxlPVwiZm9udC1mYW1pbHk6QXJpYWwsJnF1b3Q7SGVsdmV0aWNhIE5ldWUmcXVvdDssSGVsdmV0aWNhLFRhaG9tYSxzYW5zLXNlcmlmXCI+XHVjNzNjXHViODVjIDFcdWJjODhcdWM3NTggXHVjMGFkXHVjMGJkIFx1YzgxNVx1YjgyYyBcdWFjZmNcdWM4MTVcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTU4XHVjNWVjIFx1YzgxNVx1YjgyY1x1Yzc0NCBcdWM4ODVcdWI4Y2NcdWQ1NThcdWM1ZWM8XC9zcGFuPjxcL3A+XHJcblxyXG48cD4xIDE8XC9wPlxyXG5cclxuPHA+PHNwYW4gc3R5bGU9XCJmb250LWZhbWlseTpBcmlhbCwmcXVvdDtIZWx2ZXRpY2EgTmV1ZSZxdW90OyxIZWx2ZXRpY2EsVGFob21hLHNhbnMtc2VyaWZcIj5cdWM3NDQgXHVjZDljXHViODI1XHVkNTY5XHViMmM4XHViMmU0LjxcL3NwYW4+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMzg4NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRBLVNvcnQiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSByZWNlbnRseSBsZWFybmVkIGEgbmV3IHdheSB0byBzb3J0IGFuIGFycmF5IG9mIG51bWJlcnMgaW4geW91ciBhbGdvcml0aG1zIGNvdXJzZS4gVGhlIGFsZ29yaXRobSBzb3J0cyBhbiBhcnJheSBvZiBudW1iZXJzIGJ5IHJlcGVhdGVkbHkgcGVyZm9ybWluZyB0aGUgRGVsZXRlLWFuZC1BcHBlbmQgb3BlcmF0aW9uLiBUaGUgRGVsZXRlYW5kLUFwcGVuZCBvcGVyYXRpb24gY29uc2lzdHMgb2YgdGhyZWUgc3RlcHM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+Q2hvb3NlIGFuIGVsZW1lbnQgZnJvbSB0aGUgYXJyYXkuPFwvbGk+XHJcblx0PGxpPkRlbGV0ZSB0aGUgY2hvc2VuIGVsZW1lbnQgZnJvbSB0aGUgYXJyYXkuPFwvbGk+XHJcblx0PGxpPkFwcGVuZCB0aGUgY2hvc2VuIGVsZW1lbnQgdG8gdGhlIGVuZCBvZiB0aGUgYXJyYXkuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+QmVpbmcgYSBjdXJpb3VzIHN0dWRlbnQsIHlvdSB3b25kZXIgd2hhdCBpcyB0aGUgbWluaW11bSBudW1iZXIgb2YgRGVsZXRlLWFuZC1BcHBlbmQgb3BlcmF0aW9ucyByZXF1aXJlZCB0byBzb3J0IGEgZ2l2ZW4gYXJyYXkuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBkZWNpbWFsIGludGVnZXIgUCwgKDEgJmxlOyBQICZsZTsgMTAwKSwgd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhIHNldHMgdGhhdCBmb2xsb3cuPFwvcD5cclxuXHJcbjxwPkVhY2ggZGF0YSBzZXQgc2hvdWxkIGJlIHByb2Nlc3NlZCBpZGVudGljYWxseSBhbmQgaW5kZXBlbmRlbnRseS4gRWFjaCBkYXRhIHNldCBjb25zaXN0cyBvZiB0d28gb3IgbW9yZSBsaW5lcyBvZiBpbnB1dC4gVGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIGRhdGEgc2V0IG51bWJlciwgSywgZm9sbG93ZWQgYnkgYSBzaW5nbGUgc3BhY2UsIGZvbGxvd2VkIGJ5IGFuIGludGVnZXIgTiwgKDEgJmxlOyBOICZsZTsgMTAwMCksIHdoaWNoIGlzIHRoZSBsZW5ndGggb2YgdGhlIGFycmF5IHRvIHNvcnQuIFRoZSByZW1haW5pbmcgbGluZXMgaW4gdGhlIGRhdGFzZXQgY29udGFpbnMgTiBwb3NpdGl2ZSBpbnRlZ2VycyB0aGF0IGNvbXByaXNlIHRoZSBhcnJheSB0byBiZSBzb3J0ZWQsIDEwIHZhbHVlcyBwZXIgbGluZSwgZXhjZXB0IGZvciB0aGUgbGFzdCBsaW5lIHdoaWNoIG1heSBoYXZlIGxlc3MgdGhhbiAxMCB2YWx1ZXMuIEFsbCB0aGUgYXJyYXkgZWxlbWVudHMgYXJlIG5vIGxhcmdlciB0aGFuIDEwPHN1cD45PFwvc3VwPi4gVGhlIHNhbWUgdmFsdWUgbWF5IGFwcGVhciBtb3JlIHRoYW4gb25jZSBpbiB0aGUgYXJyYXkgdG8gYmUgc29ydGVkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0IHRoZXJlIGlzIG9uZSBsaW5lIG9mIG91dHB1dC4gVGhlIHNpbmdsZSBvdXRwdXQgbGluZSBjb25zaXN0cyBvZiB0aGUgZGF0YSBzZXQgbnVtYmVyLCBLLCBmb2xsb3dlZCBieSBhIHNpbmdsZSBzcGFjZSBmb2xsb3dlZCBieSBhbiBpbnRlZ2VyIHdoaWNoIGlzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBEZWxldGUtYW5kQXBwZW5kIG9wZXJhdGlvbnMgcmVxdWlyZWQgdG8gc29ydCB0aGUgYXJyYXkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d