How many inversions? P80595


Statement
 

pdf   zip

html

Count the number of inversions of every given sequence of n integer numbers x1xn. Remember that an inversion is a pair of indices i and j such that 1 ≤ i < jn and xi > xj.

Input

Input consists of several cases, each one with n followed by the n integer numbers x1xn. 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++
    User solutions
    C++