Background

In the distant year 20,000, the 'Orion Spur' restoration project is well underway. While the physical Hyper-lanes have been established, the Interplanetary Logistics System is facing a crisis.

Supply ships are supposed to arrive at the central hub in a strict, increasing order of their Priority IDs ($1, 2, 3...$). However, due to navigation software glitches caused by the recent cosmic event, the ships are arriving in a chaotic, scrambled sequence.

You are the Lead Data Architect. You need to quantify exactly how disorganized the arrival queue is so the traffic control AI can allocate the correct amount of processing power to sort them out.

Description

You are given a sequence $A$ of $N$ distinct integers, representing the Priority IDs of the ships in the order they currently appear in the arrival queue.

We define the "Chaos Metric" (mathematically known as the number of Inversions) as the number of pairs of indices $(i, j)$ such that:

1. $i < j$ (Ship $i$ arrived before Ship $j$)
2. $A[i] > A[j]$ (Ship $i$ has a higher ID/lower priority than Ship $j$)

In simpler terms, the Chaos Metric counts how many pairs of ships are in the "wrong relative order."

Your task is to calculate this total Chaos Metric.

Note: The Chaos Metric can be very large, potentially exceeding the range of a 32-bit integer.

Format

Input

• The first line contains one integer $N$ ($1 \le N \le 100,000$), the number of ships.
• The second line contains $N$ distinct integers separated by spaces, representing the sequence of Priority IDs.

Output

• Output a single integer: the total Chaos Metric (number of inversions).

Samples

5
2 4 1 3 5

3

Explanation for Sample 1: The sequence is [2, 4, 1, 3, 5]. The pairs that are out of order are:

1. (2, 1): 2 is before 1, but 2 > 1.
2. (4, 1): 4 is before 1, but 4 > 1.
3. (4, 3): 4 is before 3, but 4 > 3. Total inversions = 3.

5
12 8 3 2 1

10

Explanation for Sample 2: The array is strictly decreasing. Every pair is an inversion.

Hint

1. Why Python's sort() isn't enough: Simply calling A.sort() will give you the sorted order, but it destroys the information about the original relative positions. You need to count the "swaps" or "inversions" required to reach that sorted state.

2. Efficiency: A brute-force solution using nested loops checks every pair, resulting in $O(N^2)$ time complexity. With $N=100,000$, this will exceed the time limit (taking roughly 10 billion operations). You need an algorithm with $O(N \log N)$ complexity.

3. Merge Sort approach:

   Consider the Merge Sort algorithm. It divides the array into halves and then merges two sorted halves. During the Merge step, imagine you are merging a Left Half [L...] and a Right Half [R...]. If you pick an element from the Right Half to place in the sorted array before you pick the remaining elements in the Left Half, it implies that this Right element is smaller than all the remaining elements in the Left Half. Therefore, for that specific move, you found len(left_remaining) inversions.

Limitation

1s, 128MiB for each test case.