UVa 299

Summary

This problem amounts to counting the number of inversions in the dataset. ${\displaystyle L\leq 50}$, so we can do this trivially using an ${\displaystyle O(N^{2})}$ algorithm, such as bubble sort or insertion sort.

Explanation

Counting the number of inversions simply counts the number of swaps it takes in sorting, which is straightforward for bubble sort - increment a counter everytime you swap two adjacent items.

In c++ you can swap easily by using algorithm library function but it is not appropriate in that problem.

Optimizations

This can also be done with ${\displaystyle O(N\log N)}$ sorting algorithms, but they are overkill as ${\displaystyle L\leq 50}$

Input

3
3
1 3 2
4
4 3 2 1
2
2 1


Output

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.