# UVa 10327

## Summary

This is the standard problem of counting the number of inversions in a string of length ${\displaystyle n\leq 1000}$. N length is medium; you can choose the brute-force ${\displaystyle O(n^{2})}$ algorithm, where you will barely get accepted, or use more optimized algorithms.

## Explanation

One of the possible solutions is using merge sort to count the number of inversions, which will lead to a nice ${\displaystyle O(n\log(n))}$ algorithm. While merging two sorted arrays, any move from the right array to the final merged array will represent a number of inversions if the left array is not empty. If, for example, the left array has 3 elements left, then the merge have fixed 3 inversions in one step.

The final inversion count is the sum of all inversions fixed by all the merges done by the algorithm.

## Gotchas

• The problem does not state the width of the integers. Better be safe and stick to long long.

## Input

3
1 2 3
3
2 3 1


## Output

Minimum exchange operations : 0
Minimum exchange operations : 2


## References

Introduction to Algorithms, Chapter 2 - Getting Started, Question 2-4, 'Inversions'