How many inversions? P80595

Statement

thehtml

Count the number of inversions of every given sequence of n integer numbers x₁ … x_n. Remember that an inversion is a pair of indices i and j such that 1 ≤ i < j ≤ n and x_i > x_j.

Input

Input consists of several cases, each one with n followed by the n integer numbers x₁ … x_n. Assume 0 ≤ n ≤ 50000.

Output

For every case, print the number of inversions of the sequence.

Public test cases

Input

4   2 3 5 7
4   7 5 3 2
3   -7 -7 -7

Output

0
6
0

Information

Author: Salvador Roura
Language: English
Official solutions: C++ Python
User solutions: C++ Python