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,\;\dots,\;i-1$에 L의 가장 작은 원소 $i-1$개가 오름차순으로 들어 있다. $i$번째 반복에서는 $i$번째 위치부터 현재 $i$번째 최솟값 원소가 있는 위치까지의 부분 리스트를 뒤집는다. 그러면 $i$번째 최솟값 원소가 $i$번째 위치에 놓이게 된다.

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

• $i = 1,~ j = 3 \longrightarrow L = [1, 2, 4, 3]$

• $i = 2,~ j = 2 \longrightarrow L = [1, 2, 4, 3]$

• $i = 3,~ j = 4 \longrightarrow L = [1, 2, 3, 4]$

우리의 아키텍처에서 알고리즘을 실행할 때 가장 비용이 많이 드는 부분은 Reverse 연산이다. 따라서 각 반복의 비용은 단순히 Reverse에 전달되는 부분 리스트의 길이, 즉 값 $j - i + 1$로 정의한다. 전체 알고리즘의 비용은 각 반복 비용의 합이다.

위 예제에서 각 반복의 비용은 순서대로 $3$, $1$, $2$이고, 총비용은 $6$이다.

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

제한

시간 제한: 10초. 메모리 제한: 1 GB.

테스트 세트 1 (결과 공개)

$1 \le \mathbf{T} \le 100$. $2 \le \mathbf{N} \le 100$. 모든 $i$에 대해 $1 \le \mathbf{L_i} \le N$. 모든 $i \ne j$에 대해 $\mathbf{L_i} \ne \mathbf{L_j}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 2개의 줄로 구성된다. 첫 번째 줄에는 입력 리스트의 원소 수를 나타내는 정수 $\mathbf{N}$ 하나가 주어진다. 두 번째 줄에는 입력 리스트 $L$의 원소를 순서대로 나타내는 서로 다른 정수 $\mathbf{N}$개, $\mathbf{L_1}$, $\mathbf{L_2}$, ..., $\mathbf{L_N}$이 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 입력으로 주어진 리스트에 Reversort를 실행하는 총비용이다.

예제 케이스 #1은 위의 문제 설명에 기술되어 있다.

예제 케이스 #2에서는 한 번의 반복만 수행하며, 이때 크기가 1인 부분 리스트에 Reverse를 적용한다. 따라서 총비용은 1이다.

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