Challenge: Count the Swaps

Lab Python Intermediate 20 points

How “unsorted” is a list? Read a list and print how many swaps bubble sort makes to sort it. (This number is the count of pairs that are in the wrong order.)

Input

One line of whole numbers (at most 300).

Output

The number of swaps.

Example

Input

5 1 4 2 8

Output

Sample input available Sample output available

Editor

Python

Hints

Run bubble sort and add 1 every time you swap.

Equal neighbours are not swapped.

Solution explanation

Each swap fixes exactly one wrong-order pair, so the count equals the number of such pairs. (Module 8 shows how to count them faster.)

Show solution

a = list(map(int, input().split()))
swaps = 0
n = len(a)
for done in range(n - 1):
    for i in range(n - 1 - done):
        if a[i] > a[i + 1]:
            a[i], a[i + 1] = a[i + 1], a[i]
            swaps += 1
print(swaps)

Output

Answer