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