Up and Down Sequence

You are given a sequence $A = [A_1, A_2, \dots, A_N]$ of $N$ distinct integers. Rearrange it into an up and down sequence, that is, a sequence satisfying $A_1 < A_2 < \dots < A_m > A_{m+1} > \dots > A_N$ for some index $m$ with $1 \le m \le N$. The values increase up to one position and decrease after it.

Only one operation is allowed. You may swap two adjacent elements of the sequence. Find the minimum number of such swaps needed to reach an up and down sequence.

The first line contains the number of test cases $T$. $T$ test cases follow. The first line of each test case contains the integer $N$, and the second line contains $N$ distinct integers $A_1, A_2, \dots, A_N$ separated by spaces.

Limits

• $1 \le T \le 100$
• $1 \le N \le 10$
• $1 \le A_i \le 10^9$
• The $A_i$ are pairwise distinct.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of adjacent swaps needed to rearrange $A$ into an up and down sequence.

In the first case of the sample, the sequence is already up and down (with $m = N = 3$), so no swap is needed. In the second case, swapping 3 and 7 gives 1 8 10 7 3, which is up and down with $m = 3$.