Almost Sorted

Almost Sorted

Given an array of n integers, find the minimum number of adjacent swaps ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌‌​​​​‌‌​​‌​​​​‌‌​​​‌​​‌‌​‌‌​​‌‌​​‌​​​​‌‌‌​​‌​​‌‌‌​​‌​‌‌​​​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​‌​‌​​‌‌​‌‌​​​‌‌​​‌‌​​‌‌‌​​​​​‌‌​​‌‌needed to sort it in non-decreasing order. (This is a classic fact: that minimum equals the number of inversions — pairs i < j with a[i] > a[j].)

Input

Line 1: integer n (1 ≤ n ≤ 2·10^5) Line 2: n integers ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌‌​​​​‌‌​​‌​​​​‌‌​​​‌​​‌‌​‌‌​​‌‌​​‌​​​​‌‌‌​​‌​​‌‌‌​​‌​‌‌​​​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​‌​‌​​‌‌​‌‌​​​‌‌​​‌‌​​‌‌‌​​​​​‌‌​​‌‌a_1 … a_n (-10^9 ≤ a_i ≤ 10^9)

Output

A single integer: the minimum number of adjacent swaps to sort the array.

Example

Input:

5
5 4 3 2 1

Output:

10

Constraints

• 1 ≤ n ≤ 2·10^5 ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌‌​​​​‌‌​​‌​​​​‌‌​​​‌​​‌‌​‌‌​​‌‌​​‌​​​​‌‌‌​​‌​​‌‌‌​​‌​‌‌​​​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​‌​‌​​‌‌​‌‌​​​‌‌​​‌‌​​‌‌‌​​​​​‌‌​​‌‌- The answer may exceed the range of a 32-bit signed integer — use a 64-bit type. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​​‌‌‌​​​​‌‌​​‌​​​​‌‌​​​‌​​‌‌​‌‌​​‌‌​​‌​​​​‌‌‌​​‌​​‌‌‌​​‌​‌‌​​​​‌​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌‌​​‌‌​‌​‌​​‌‌​‌‌​​​‌‌​​‌‌​​‌‌‌​​​​​‌‌​​‌‌

5
5 4 3 2 1

10

5
1 2 3 4 5

0