시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 45 13 13 52.000%

문제

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

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

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

입력

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

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

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

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

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

출력

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

예제 입력

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
2 3
3 15

힌트

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

1 3

1 3 2

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

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

1 2 3

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

1 1

을 출력합니다.