export function countInversions(nums: number[]): number {
  let pre_rest = 0
  function rec(lst){
    if(lst.length <= 1){
      return lst
    }
    let size    = lst.length
    let left_m  = rec(lst.slice(0,parseInt(size/2)))
    let right_m = rec(lst.slice(parseInt(size/2),size))
    let il       = 0
    let ir       = 0
    let sub_rest = []
    while(il<left_m.length || ir<right_m.length){
      if(ir<right_m.length && il<left_m.length){
        if(left_m[il]>right_m[ir]){
          pre_rest+=left_m.length-il
          sub_rest.push(right_m[ir])
          ir++
        }else{
          sub_rest.push(left_m[il])
          il++
        }
      }else{
        if(ir<right_m.length){
          sub_rest.push(right_m[ir])
          ir++
        }
        if(il<left_m.length){
          sub_rest.push(left_m[il])
          il++
        }
      }
    }
    return sub_rest
  }
  rec(nums)
  return pre_rest
}