Challenge: Count the Swaps

Lab C++ Intermediate 20 points

Print how many swaps bubble sort makes to sort n numbers (this equals the number of pairs in the wrong order).

Input

Line 1: n (n ≤ 2000). Line 2: n whole numbers.

Output

The number of swaps.

Example

Input

5
5 1 4 2 8

Output

Sample input available Sample output available

Editor

C++

Hints

Run bubble sort and count every swap.

Equal neighbours are not swapped.

Solution explanation

Each swap fixes exactly one wrong-order pair. Module 8 counts them faster with merge sort.

Show solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    long long swaps = 0;
    for (int done = 0; done < n - 1; done++)
        for (int i = 0; i < n - 1 - done; i++)
            if (v[i] > v[i + 1]) { swap(v[i], v[i + 1]); swaps++; }
    cout << swaps << endl;
    return 0;
}

Output

Answer