Reversort

참고: "Reversort"와 "Reversort Engineering" 문제의 지문은 마지막 문단을 제외하면 동일하다. 두 문제는 서로 독립적으로 풀 수 있다.

Reversort는 서로 다른 정수로 이루어진 리스트를 오름차순으로 정렬하는 알고리즘이다. 이 알고리즘은 "Reverse" 연산을 바탕으로 한다. 이 연산을 한 번 적용하면 리스트의 어떤 연속한 부분의 순서가 뒤집힌다.

알고리즘의 의사코드는 다음과 같다.

Reversort(L):
  for i := 1 to length(L) - 1
    j := position with the minimum value in L between i and length(L), inclusive
    Reverse(L[i..j])

i-1번 반복한 뒤에 리스트의 1,2,…,i-1번 위치에는 L에서 가장 작은 i-1개의 원소가 오름차순으로 들어 있다. i번째 반복에서는 i번 위치부터 i번째로 작은 원소가 현재 있는 위치까지의 부분 리스트를 뒤집는다. 그러면 i번째로 작은 원소가 i번 위치에 오게 된다.

예를 들어 원소가 4개인 리스트에서는 이 알고리즘이 3번 반복한다. L=[4,2,1,3]을 처리하는 과정은 다음과 같다.

1. i=1, j=3 ⟶ L=[1,2,4,3]
2. i=2, j=2 ⟶ L=[1,2,4,3]
3. i=3, j=4 ⟶ L=[1,2,3,4]

우리 구조에서 이 알고리즘을 실행할 때 가장 비용이 큰 부분은 Reverse 연산이다. 따라서 각 반복의 비용은 Reverse에 넘겨지는 부분 리스트의 길이, 즉 j−i+1로 정의한다. 알고리즘 전체의 비용은 각 반복 비용의 합이다.

위 예에서 각 반복의 비용은 차례로 3, 1, 2이고 합계는 6이다.

초기 리스트가 주어졌을 때, Reversort를 실행하는 비용을 계산하라.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 그다음 T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 2개의 줄로 이루어진다. 첫 줄에는 입력 리스트의 원소 개수를 나타내는 정수 N이 하나 주어진다. 둘째 줄에는 입력 리스트 L의 원소 L1, L2, ..., LN이 순서대로 주어진다. 이 값들은 서로 다른 N개의 정수이다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 주어진 리스트에 Reversort를 실행하는 총비용이다.

예제 1은 위 지문에 설명되어 있다.

예제 2에서는 반복이 한 번뿐이고, Reverse가 크기 1인 부분 리스트에 적용된다. 따라서 총비용은 1이다.

예제 3에서는 첫 반복이 리스트 전체를 뒤집으므로 비용이 7이다. 그 뒤 리스트는 이미 정렬되어 있지만 반복이 5번 더 남아 있고, 각각의 비용은 1이다.