Basim is new to programming. After learning about basic problem solving and data structures, he is now learning about different algorithms. Currently he is exploring sorting algorithms.
While exploring he found a term “Inversion count”. He found the line “Inversion Count for an array indicates – how far (or close) the array is from being sorted. If the array is already sorted, then the inversion count is 0, but if the array is sorted in reverse order, the inversion count is the maximum.” on the internet.
Basim has an array containing distinct integers from to .
Basim currently knows only one sorting algorithm, Bubble sort. So he is trying to figure out the inversion count in his array according to his learning. That is he will find out the number of swaps while applying bubble sort in his array.
Given Basim’s array you have to find out the number of swaps done while applying bubble sort on the array.
The first line of input contains a single integer — the number of elements in Basim’s array. The second line contains integers , , , …., .( means the element of the array)
and array elements are unique.
You need to print the number of inversions, in other words, number of swaps while performing bubble sort.
Input | Output |
---|---|
5 4 3 1 5 2 | 6 |
4 3 1 5 2 Here the swaps are shown sequentially in the bubble sort process and the swap count is 6. |
Be careful about the newline(‘\n’) at the end.