A shuffled manuscript lists n page numbers in the order the pages were stacked. Two pages form an out-of-order pair if the page that appears earlier in the stack carries a strictly larger number than a page that appears later. Counting these pairs measures how far the stack is from sorted.

Count the number of pairs (i, j) with i < j (by stack position) and page[i] > page[j]. Page numbers may repeat; only strictly-greater pairs count. The intended approach counts these pairs while performing a merge sort.

Input format

Line 1: an integer n, the number of pages. Line 2: n space-separated integers, the page numbers in stack order.

Output format

A single integer: the number of out-of-order pairs.

Constraints

• 1 <= n <= 100000
• 0 <= each page number <= 1000000000

5
2 4 1 3 5

3

4
1 2 3 4

0