Limits 1s, 512 MB

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 N\bf{N} distinct integers from 1\bf{1} to N\bf{N}.

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.

Input

The first line of input contains a single integer N\bf{N} — the number of elements in Basim’s array. The second line contains N\bf{N} integers a1\bf{a_1}, a2\bf{a_2}, a3\bf{a_3}, …., an\bf{a_n}.(ai\bf{a_i} means the ith\bf{i^{th}} element of the array)

2N100\bf{2 \le N \le 100}

1aiN\bf{1 \le a_i \le N} and array elements are unique.

Output

You need to print the number of inversions, in other words, number of swaps while performing bubble sort.

Sample

InputOutput
5
4 3 1 5 2
6

4 3 1 5 2
3-4 1 5 2
3 1-4 5 2
3 1 4 2-5
1-3 4 2 5
1 3 2-4 5
1 2-3 4 5

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.

Submit

Login to submit.

Statistics

95% Solution Ratio
Rakib.4411Earliest, Nov '22
Moinul_6039Fastest, 0.0s
tusharLightest, 4.9 MB
rubayed.423650Shortest, 276B
Toph uses cookies. By continuing you agree to our Cookie Policy.