Write in Java. Program need to have runtimes < n^2 to satisfy the runtime efficiency of some of the testsets.

Question 2: Understanding Orders

Given an array A of size N, find the number of ordered pairs (i, j) such that i < j and A[i] < A[j].

Input:

First line contains one integer, N, size of array.

Second line contains N space separated integers denoting the elements of the array A.

Output:

Print the total number of ordered pairs (i, j) such that i < j and A[i] < A[j].

Constraints:

1. 1 ? N ? 10^6

2. ?105 ? A[i] ? 106

Input

5

4 1 3 2 5

output

6

The 6 cases are: 4 < 5, 1 < 3, 1 < 2, 1 < 5, 3 < 5, 2 < 5.