The Door of the Divine Temple

After deciphering the ancient Rune's Code, little FF has uncovered a secret underground passage. At the very bottom, he encountered a massive stone door adorned with an ancient scene showing people performing a mysterious ritual. Above the door, in archaic script, the words "Temple of the Gods" are inscribed.

The inscription hints that only a truly wise candidate – one who can perform a specific ritual – may open the door. The ritual involves taking a sequence of n numbers (engraved on the door) and, through a series of adjacent swaps, converting it into a non-decreasing sequence. In fact, the minimal number of adjacent swaps required is equal to the number of inversions in the sequence, i.e., $$I=\sum_{ia_j].$$

Your task is to help little FF by calculating this minimal number of swaps.

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of numbers.

The second line contains n space-separated integers, representing the sequence inscribed on the door.

outputFormat

Output a single integer representing the minimum number of adjacent swaps required to transform the sequence into a non-decreasing order.

sample

3
1 3 2

1