#### Round 2, 2014

Submit Solution(Code Jam Page)

### Problem

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.

### Input

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.

### Output

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.

### Limits

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

1 ≤ N ≤ 10.

1 ≤ N ≤ 1000.

### Sample

 Input Output ```2 3 1 2 3 5 1 8 10 3 7 ``` ```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).

Points Correct Attempted
7pt 1728 2380
11pt 1351 1426

### Subscribe to our newsletter

Join our monthly newsletter and never miss out on new stories and promotions.