/*----------------------------------------------------------------
* Author: Sheng Yu - codesays.com
* Written: 09/05/2014
* Last updated: 09/05/2014
*
* Filename: InversePairs.java
* Compilation: javac InversePairs.java
* Execution: java InversePairs
* JDK Used: 1.7
*----------------------------------------------------------------*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
/**
* The utility to count the inverse pairs in an integer array.
* @author Sheng Yu codesays.com
*/
public class InversePairs {
/**
* Count the inverse pairs in the given array. Do a merge sort, and count
* the sum of swap distance.
* @param input an array of integers
* @return the number of inverse pairs in the input array.
*/
public long countInversePairs(int[] input) {
int[] temp = new int[input.length];
int segLen = 1;
long count = 0;
// Do a bottom-up merge sort
while (segLen < input.length) {
for (int begin = 0; begin < input.length; begin += (segLen << 1)) {
int firstBegin = begin;
int firstEnd = begin + segLen;
if (firstEnd >= input.length) break;
int secondBegin = begin + segLen;
int secondEnd = Math.min(secondBegin + segLen, input.length);
int resultBegin = begin;
// Merge sort these two sub-array to the temp array.
int tempIndex = 0;
while (firstBegin < firstEnd && secondBegin < secondEnd) {
if (input[firstBegin] <= input[secondBegin]) {
temp[tempIndex++] = input[firstBegin++];
} else {
temp[tempIndex++] = input[secondBegin++];
count += firstEnd - firstBegin;
}
}
while (firstBegin < firstEnd) {
temp[tempIndex++] = input[firstBegin++];
}
while (secondBegin < secondEnd) {
temp[tempIndex++] = input[secondBegin++];
}
// Write the temp array back to original positions
for (int i = 0; i < tempIndex; ++i) {
input[resultBegin + i] = temp[i];
}
}
segLen *= 2;
}
return count;
}
/**
* Stub for test.
* @param args the command line arguments.
* @throws IOException when input gets error.
*/
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
int[] unsorted = null;
int inputSize = 0;
InversePairs pairs = new InversePairs();
while (st.nextToken() != StreamTokenizer.TT_EOF) {
inputSize = (int) st.nval;
unsorted = new int[inputSize];
for (int i = 0; i < inputSize; ++i) {
st.nextToken();
unsorted[i] = (int) st.nval;
}
System.out.println(pairs.countInversePairs(unsorted));
}
}
}