Challenge: Count Wrong-Order Pairs Fast

Lab C++ Advanced 30 points

Count the pairs (i, j) with i < j and a[i] > a[j] – the same number as bubble sort's swaps – but for up to 100,000 numbers, where O(n²) is too slow. Count them while merge sorting: when an item from the right half is taken before items left in the left half, it forms a wrong-order pair with each of them.

Input

Line 1: n. Line 2: n whole numbers.

Output

The number of pairs.

Example

Input

5
5 1 4 2 8

Output

Sample input available Sample output available

Editor

C++

Hints

Write merge sort that also returns a count.

When you take v[j] from the right half, add (mid - i).

Use long long – the count can reach about 5 × 10⁹.

Solution explanation

Merge sort's O(n log n) structure counts all pairs without looking at each one.

Show solution

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

long long sortCount(vector<int>& v, int lo, int hi) {
    if (hi - lo <= 1) return 0;
    int mid = (lo + hi) / 2;
    long long count = sortCount(v, lo, mid) + sortCount(v, mid, hi);
    vector<int> m;
    int i = lo, j = mid;
    while (i < mid && j < hi) {
        if (v[i] <= v[j]) m.push_back(v[i++]);
        else {
            count += mid - i;          // v[j] is smaller than every item left in the left half
            m.push_back(v[j++]);
        }
    }
    while (i < mid) m.push_back(v[i++]);
    while (j < hi) m.push_back(v[j++]);
    for (int k = 0; k < (int)m.size(); k++) v[lo + k] = m[k];
    return count;
}

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int& x : v) cin >> x;
    cout << sortCount(v, 0, n) << endl;
    return 0;
}

Output

Answer