Submit solution

Points: 35
Time limit: 1.0s
Memory limit: 256M

Problem type

During this pandemic, citizens got messages on their phones to go get their money from ATMs. A security agent in front of an ATM was distributing numbers to organize the waiting line. However, things got messed up, so the line got random organized.

The security agent wants to re-organize the line. Your task is to help him achieve that by counting the number of pairs that should be swapped in order to make the line organized again. However, the security agent is only allowed to do adjacent swaps.

A line is said to be organized if the numbers are sorted in a non decreasing order.

Input Specification

The first line contains an integer \(N\) \((1\le N\le 10^5)\), the length of the queue. The next line contains \(N\) space separated integers \((1\le S_{i} \le 10^9)\) denoting the waiting numbers.

Output Specification

Print the number of described pairs as defined in the problem statement.

Sample Input

10 6 4

Sample Output


Sample Input

2 8 4 20 1

Sample Output



In the first sample, for example we can swap 4 with 6, then 4 with 10, and then 6 and 10.


There are no comments at the moment.