CareerCup

I am not sure about linear but you can do it O(nlogn)
1.traverse from back and construct a binary search tree.
2. for each number in the array .. find it in binary search tree keeping count of number of right calls(In binary search tree depending on the condition , we make one of the two calls (left or right) ;add this count to sum
3. after the iteration of the array. sum is the answer

Not possible in O(N).
There is a O(NlogN) solution, read in Cormen about 'inversions' problem in the merge sort chapter.

import java.util.Arrays;

public class Inversions {
	public static int getInversions(int a[]) {
		if (a.length <= 1) {
			return 0;
		}

		int aleft[] = Arrays.copyOfRange(a, 0, a.length >> 1);
		int aright[] = Arrays.copyOfRange(a, a.length >> 1, a.length);

		int inversions = 0;
		inversions += getInversions(aleft);
		inversions += getInversions(aright);

		int i1 = 0, i2 = 0, i = 0;
		while (i1 < aleft.length && i2 < aright.length) {
			if (aleft[i1] <= aright[i2]) {
				a[i++] = aleft[i1++];
			} else {
				a[i++] = aright[i2++];
				inversions += (aleft.length - i1);
			}
		}
		while (i1 < aleft.length) {
			a[i++] = aleft[i1++];
		}
		while (i2 < aright.length) {
			a[i++] = aright[i2++];
		}

		return inversions;
	}

	public static void main(String args[]) {
		System.out.println(getInversions(new int[] { 2, 3, 8, 6, 1 }));
		System.out.println(getInversions(new int[] { 5, 4, 3, 5, 6, 7, 6, 4 }));
	}
}

question is not about the cosnuctive pairs it can be possible when i =1 and j =5 and a[1] > a[5]

You can do it in NlogN using Divide and conquer method(Merge Sort).

#include <iostream>

using namespace std;

int main( int argc, char* argv[] )
{
const int A[] = {5,4,3,5,6,7,6,4};

int count = 0;

for(int i = 0; i < 8; i++) {

if( i == 7 ) {
// stop
break;
}

if( A[i] > A[i+1] ) {
count++;
}
}

cout << "Count: " << count;

return 0;
}