import java.util.*;
//Uses a modified Merge-Sort Algorithm to calculate number of inversions
class soln
{
//Modified Merge method.
static long merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0;
long count = 0; //Initialize
while (i < left.length || j < right.length) {
//Loop till all elements in both subarrays are taken
if (i == left.length) {
arr[i+j] = right[j];
j++; //Left subarray was fully traversed
} else if (j == right.length) {
arr[i+j] = left[i];
i++; //Right subarray was fully traversed
} else if (left[i] <= right[j]) {
arr[i+j] = left[i];
i++; //Left element is less than Right element
//Hence, no inversion. No count increment.
} else {
arr[i+j] = right[j];
count += left.length-i;
//Increment count with the number of inversions
j++;
}
}
return count;
}
static long invCount(int[] arr) {
if (arr.length < 2)
return 0;
int m = (arr.length + 1) / 2;
//Split array into 2 subarrays. D n C.
int left
[] = Arrays.
copyOfRange(arr,
0, m
); int right
[] = Arrays.
copyOfRange(arr, m, arr.
length);
return invCount(left) + invCount(right) + merge(arr, left, right);
}
public static void main
(String[] args
) {
Scanner sc
= new Scanner
(System.
in); int n = sc.nextInt(); //Input n taken
int a[] = new int[n];
for(int i=0;i<n;i++)
a[i] = sc.nextInt(); //Array of integers taken
System.
out.
println(invCount
(a
)); //Function returns long }
}
aW1wb3J0IGphdmEudXRpbC4qOwovL1VzZXMgYSBtb2RpZmllZCBNZXJnZS1Tb3J0IEFsZ29yaXRobSB0byBjYWxjdWxhdGUgbnVtYmVyIG9mIGludmVyc2lvbnMKY2xhc3Mgc29sbgp7CgkvL01vZGlmaWVkIE1lcmdlIG1ldGhvZC4KCXN0YXRpYyBsb25nIG1lcmdlKGludFtdIGFyciwgaW50W10gbGVmdCwgaW50W10gcmlnaHQpIHsKICAgIGludCBpID0gMCwgaiA9IDA7CiAgICBsb25nIGNvdW50ID0gMDsgLy9Jbml0aWFsaXplCiAgICB3aGlsZSAoaSA8IGxlZnQubGVuZ3RoIHx8IGogPCByaWdodC5sZW5ndGgpIHsgIAogICAgCS8vTG9vcCB0aWxsIGFsbCBlbGVtZW50cyBpbiBib3RoIHN1YmFycmF5cyBhcmUgdGFrZW4KICAgICAgICBpZiAoaSA9PSBsZWZ0Lmxlbmd0aCkgewogICAgICAgICAgICBhcnJbaStqXSA9IHJpZ2h0W2pdOwogICAgICAgICAgICBqKys7IC8vTGVmdCBzdWJhcnJheSB3YXMgZnVsbHkgdHJhdmVyc2VkCiAgICAgICAgfSBlbHNlIGlmIChqID09IHJpZ2h0Lmxlbmd0aCkgewogICAgICAgICAgICBhcnJbaStqXSA9IGxlZnRbaV07CiAgICAgICAgICAgIGkrKzsgLy9SaWdodCBzdWJhcnJheSB3YXMgZnVsbHkgdHJhdmVyc2VkCiAgICAgICAgfSBlbHNlIGlmIChsZWZ0W2ldIDw9IHJpZ2h0W2pdKSB7CiAgICAgICAgICAgIGFycltpK2pdID0gbGVmdFtpXTsKICAgICAgICAgICAgaSsrOyAvL0xlZnQgZWxlbWVudCBpcyBsZXNzIHRoYW4gUmlnaHQgZWxlbWVudAogICAgICAgICAgICAvL0hlbmNlLCBubyBpbnZlcnNpb24uIE5vIGNvdW50IGluY3JlbWVudC4gICAgICAgICAgICAgICAKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICBhcnJbaStqXSA9IHJpZ2h0W2pdOwogICAgICAgICAgICBjb3VudCArPSBsZWZ0Lmxlbmd0aC1pOwogICAgICAgICAgICAvL0luY3JlbWVudCBjb3VudCB3aXRoIHRoZSBudW1iZXIgb2YgaW52ZXJzaW9ucwogICAgICAgICAgICBqKys7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGNvdW50Owp9CgkKCQoJc3RhdGljIGxvbmcgaW52Q291bnQoaW50W10gYXJyKSB7CiAgICBpZiAoYXJyLmxlbmd0aCA8IDIpCiAgICAgICAgcmV0dXJuIDA7CiAKICAgIGludCBtID0gKGFyci5sZW5ndGggKyAxKSAvIDI7CiAgICAvL1NwbGl0IGFycmF5IGludG8gMiBzdWJhcnJheXMuIEQgbiBDLgogICAgaW50IGxlZnRbXSA9IEFycmF5cy5jb3B5T2ZSYW5nZShhcnIsIDAsIG0pOwogICAgaW50IHJpZ2h0W10gPSBBcnJheXMuY29weU9mUmFuZ2UoYXJyLCBtLCBhcnIubGVuZ3RoKTsKIAogICAgcmV0dXJuIGludkNvdW50KGxlZnQpICsgaW52Q291bnQocmlnaHQpICsgbWVyZ2UoYXJyLCBsZWZ0LCByaWdodCk7Cgl9CgkKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB7CgkJCgkJU2Nhbm5lciBzYyAgPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwoJCWludCBuID0gc2MubmV4dEludCgpOyAvL0lucHV0IG4gdGFrZW4KCQlpbnQgYVtdID0gbmV3IGludFtuXTsKCQlmb3IoaW50IGk9MDtpPG47aSsrKQoJCQlhW2ldID0gc2MubmV4dEludCgpOyAvL0FycmF5IG9mIGludGVnZXJzIHRha2VuCgkJCQoJCVN5c3RlbS5vdXQucHJpbnRsbihpbnZDb3VudChhKSk7IC8vRnVuY3Rpb24gcmV0dXJucyBsb25nCiAgICB9Cn0gCiA=