#213370. [GCJ 2014 #2] Up and Down

You are given a sequence of distinct integers , and would like to rearrange it into an up and down sequence (one where for some index , with between 1 and 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, . test cases follow. Each test case begins with a line containing a single integer: . The next line contains distinct integers: .

For each test case, output one line containing "Case #: ", where is the test case number (starting from 1) and is the minimum number of swaps required to rearrange 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

Sample Explanation

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

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

Limits

• .
• .
• The will be pairwise distinct.

Small dataset(7 Pts)

• Time limit: 60 3 seconds.
• .

Large dataset(11 Pts)

• Time limit: 120 5 seconds.
• .