#include "iostream"
using namespace std;
int total_inversions = 0;
int count_inversion_merge(int array[], int mid, int n) {
int i = 0, j = mid, k, inversion = 0;
int b[n];
for (k = 0; k < n; k++) {
if (j == n || (i < mid && array[i] < array[j])) {
b[k] = array[i];
i++;
} else {
b[k] = array[j];
j++;
inversion+=mid-i;
}
}
return inversion;
}
int count_inversion(int a[], int n) {
if (n <= 1) {
return 0;
}
count_inversion(a, n / 2);
count_inversion(a + (n / 2), n - n / 2);
total_inversions+=count_inversion_merge(a, n / 2, n);
return total_inversions;
}
int main() {
// int a[] ={ 2, 4, 1, 3, 5 };
int a[] ={ 1, 20, 6, 4, 5 };
cout << count_inversion(a, 5);
return 0;
}
I2luY2x1ZGUgImlvc3RyZWFtIgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCB0b3RhbF9pbnZlcnNpb25zID0gMDsKaW50IGNvdW50X2ludmVyc2lvbl9tZXJnZShpbnQgYXJyYXlbXSwgaW50IG1pZCwgaW50IG4pIHsKICAgIGludCBpID0gMCwgaiA9IG1pZCwgaywgaW52ZXJzaW9uID0gMDsKICAgIGludCBiW25dOwogICAgZm9yIChrID0gMDsgayA8IG47IGsrKykgewogICAgICAgIGlmIChqID09IG4gfHwgKGkgPCBtaWQgJiYgYXJyYXlbaV0gPCBhcnJheVtqXSkpIHsKICAgICAgICAgICAgYltrXSA9IGFycmF5W2ldOwogICAgICAgICAgICBpKys7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgYltrXSA9IGFycmF5W2pdOwogICAgICAgICAgICBqKys7CiAgICAgICAgICAgIGludmVyc2lvbis9bWlkLWk7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGludmVyc2lvbjsKfQoKCmludCBjb3VudF9pbnZlcnNpb24oaW50IGFbXSwgaW50IG4pIHsKICAgIGlmIChuIDw9IDEpIHsKICAgICAgICByZXR1cm4gMDsKICAgIH0KICAgIGNvdW50X2ludmVyc2lvbihhLCBuIC8gMik7CiAgICBjb3VudF9pbnZlcnNpb24oYSArIChuIC8gMiksIG4gLSBuIC8gMik7CiAgICB0b3RhbF9pbnZlcnNpb25zKz1jb3VudF9pbnZlcnNpb25fbWVyZ2UoYSwgbiAvIDIsIG4pOwogICAgcmV0dXJuIHRvdGFsX2ludmVyc2lvbnM7Cgp9CmludCBtYWluKCkgewoKLy8gICAgaW50IGFbXSA9eyAyLCA0LCAxLCAzLCA1IH07CiAgICBpbnQgYVtdID17IDEsIDIwLCA2LCA0LCA1IH07CiAgICBjb3V0IDw8IGNvdW50X2ludmVyc2lvbihhLCA1KTsKCiAgICByZXR1cm4gMDsKfQo=