시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 10 9 9 90.000%

## 문제

You are given a sequence of distinct integers A = [A1, A2, ..., AN], and would like to rearrange it into an up and down sequence (one where A1 < A2 < ... < Am > Am+1 > ... > AN for some index m, with m between 1 and N inclusive).

The rearrangement is accomplished by swapping two adjacent elements of the sequence at a time. Predictably, you are particularly interested in the minimum number of such swaps needed to reach an up and down sequence.

## 입력

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing a single integer: N. The next line contains N distinct integers: A1, ..., AN.

Limits

• 1 ≤ T ≤ 100.
• 1 ≤ Ai ≤ 109
• The Ai will be pairwise distinct.
• 1 ≤ N ≤ 10.

## 출력

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of swaps required to rearrange A into an up and down sequence.

## 예제 입력 1

2
3
1 2 3
5
1 8 10 3 7


## 예제 출력 1

Case #1: 0
Case #2: 1


## 힌트

In the first case, the sequence is already in the desired form (with m=N=3) so no swaps are required.

In the second case, swapping 3 and 7 produces an up and down sequence (with m=3).

## 채점 및 기타 정보

• 예제는 채점하지 않는다.