该题目来源于牛客网《剑指offer》专题。

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007。

输入描述:

题目保证输入的数组中没有的相同的数字。

数据范围：

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

示例：

输入

1,2,3,4,5,6,7,0

输出

7

Go语言实现：

func inversePairs(s []int) int {

   if s == nil || len(s) == 0 {

      return 0

   }

   length := len(s)

   copy := []int{}

   for _, v := range s {

      copy = append(copy, v)

   }

   high := length - 1

   count := inversePairsHandler(s, copy, 0, high)

   return count

}

func inversePairsHandler(s, copy []int, low, high int) int {

   if low == high {

      return 0

   }

   mid := (low + high) / 2

   leftCount := inversePairsHandler(s, copy, low, mid) % 1000000007

   rightCount := inversePairsHandler(s, copy, mid+1, high) % 1000000007

   count := 0

   i := mid

   j := high

   locCopy := high

   for i >= low && j > mid {

      if s[i] > s[j] {

         count += j - mid

         locCopy--

         i--

         copy[locCopy] = s[i]

         if count >= 1000000007 {

            count %= 1000000007

         }

      } else {

         locCopy--

         j--

         copy[locCopy] = s[i]

      }

   }

   for ; i >= low; i-- {

      locCopy--

      copy[locCopy] = s[i]

   }

   for ; j > mid; j-- {

      locCopy--

      copy[locCopy] = s[j]

   }

   for index := low; index <= high; index++ {

      s[index] = copy[index]

   }

   return (leftCount + rightCount + count) % 1000000007

}