Up and Down (Large)

You are given a sequence of distinct integers $A = [A_1, A_2, \dots, A_N]$, and you want to rearrange it into an up and down sequence. A sequence is up and down when there is an index $m$ ($1 \le m \le N$) with

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

If $m = 1$ the whole sequence decreases, and if $m = N$ the whole sequence increases.

You may swap two adjacent elements of the sequence, one swap at a time. 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. Each test case begins with a line containing one integer $N$. The next line contains $N$ distinct integers $A_1, \dots, A_N$ separated by spaces.

Limits

• $1 \le T \le 100$
• $1 \le N \le 1000$
• $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 swaps required to rearrange $A$ into an up and down sequence.

The sequence in the first example is already in the desired form (with $m = N = 3$), so no swap is needed.

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