Brainman

Time limit1sMemory limit128 MB

Summary

Given a sequence, find the minimum number of adjacent swaps needed to sort it in non-decreasing order; this equals the number of inversions.

Level: Medium4 of 10
Topics: Divide and conquer, Sorting, Array
Solved: No attempts yet

Problem

Raymond Babbitt amazes his brother Charlie. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant, just by glancing at them, and he can even count playing cards. Charlie would love to do cool things like that too, and he wants to beat his brother at a similar task.

Here is what Charlie thinks of. You are given a sequence of $N$ numbers. The goal is to move the numbers around until the sequence is sorted in non-decreasing order. The only allowed operation is to swap two adjacent numbers.

For example, the sequence $(2\ 8\ 0\ 3)$ can be sorted with nine adjacent swaps:

Start	2	8	0	3
swap (2 8)	8	2	0	3
swap (2 0)	8	0	2	3
swap (2 3)	8	0	3	2
swap (8 0)	0	8	3	2
swap (8 3)	0	3	8	2
swap (8 2)	0	3	2	8
swap (3 2)	0	2	3	8
swap (3 8)	0	2	8	3
swap (8 3)	0	2	3	8

However, it is even possible to sort it with only three such swaps:

Start	2	8	0	3
swap (8 0)	2	0	8	3
swap (2 0)	0	2	8	3
swap (8 3)	0	2	3	8

The question is: what is the minimum number of adjacent swaps needed to sort a given sequence? Since Charlie does not have Raymond's mental capabilities, he asks you to write a program that answers the question.

Input

The first line contains the number of scenarios.

Each scenario is given on a single line: first the length $N$ ( $1 \le N \le 1000$ ) of the sequence, followed by the $N$ elements of the sequence (each element is an integer in $[-1000000, 1000000]$ ). All numbers on the line are separated by single spaces.

Output

For each scenario, print a line Scenario #i:, where i is the scenario number starting at 1, followed by a line containing the minimum number of adjacent swaps needed to sort that scenario's sequence. Separate the output of consecutive scenarios with a single blank line.

Examples1

Example 1

Input

4
4 2 8 0 3
10 0 1 2 3 4 5 6 7 8 9
6 -42 23 6 28 -100 65537
5 0 0 0 0 0

Expected output

Scenario #1:
3

Scenario #2:
0

Scenario #3:
5

Scenario #4:
0