Counting Inversions

Interview

Time limit1sMemory limit256 MB

Summary

Count the pairs in a permutation of 1 to n where a larger number stands before a smaller one.

Level: Medium4 of 10
Topics: Divide and conquer, Sorting
Solved: No attempts yet

Problem

A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once.

Two integers in а permutation form an inversion, when the bigger one is before the smaller one.

As an example, in the permutation 4 2 7 1 5 6 3, there are 10 inversions in total. They are the following pairs: 4–2, 4–1, 4–3, 2–1, 7–1, 7–5, 7–6, 7–3, 5–3, 6–3.

Write program invcnt that computes the number of the inversions in a given permutation.

Input

The value for the number n is written on the first line of the standard input. The permutation is written on the second line: n numbers, delimited by spaces.

Output

Write the count of inversions on the standard output.

Constraints

2 ≤ n ≤ 1000000

Examples4

Example 1
Input
```
7
4 2 7 1 5 6 3
```
Expected output
```
10
```
Example 2
Input
```
5
3 1 5 2 4
```
Expected output
```
4
```
Example 3
Input
```
10
1 2 3 4 5 6 7 8 9 10
```
Expected output
```
0
```
Example 4
Input
```
10
10 9 8 7 6 5 4 3 2 1
```
Expected output
```
45
```