오르내림 수열 (라지)

서로 다른 정수로 이루어진 수열 $A = [A_1, A_2, \dots, A_N]$이 주어진다. 이 수열을 오르내림 수열로 바꾸려고 한다. 오르내림 수열은 어떤 인덱스 $m$ ($1 \le m \le N$)에 대해

$A_1 < A_2 < \dots < A_m > A_{m+1} > \dots > A_N$

을 만족하는 수열이다. $m = 1$이면 수열 전체가 감소하고, $m = N$이면 수열 전체가 증가한다.

수열을 바꿀 때는 인접한 두 원소를 한 번에 하나씩 교환할 수 있다. 오르내림 수열을 만드는 데 필요한 교환 횟수의 최솟값을 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 정수 $N$이 주어지고, 다음 줄에는 서로 다른 정수 $A_1, \dots, A_N$이 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 100$
• $1 \le N \le 1000$
• $1 \le A_i \le 10^9$
• $A_i$는 모두 서로 다르다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 $A$를 오르내림 수열로 만드는 데 필요한 최소 교환 횟수이다.

첫 번째 예제의 수열은 이미 원하는 형태라서($m = N = 3$) 교환할 필요가 없다.

두 번째 예제에서는 3과 7을 교환하면 오르내림 수열이 된다($m = 3$).