inversions.hs

import System.Environment
import qualified Data.Set as Set

{-
  For each x input element
    Split current set on `x` O(log n)
    Count right side         O(1)
    Add x to set             O(log n)
-}

inv :: Ord a =>[a] ->Int
inv = fst . foldl (\(n, s) x ->(n + (S.size . snd . S.split x) s, S.insert x s)) (0, S.empty)

main = getContents >>= print . (inversions :: [Int] ->Int) . map read . words