# 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
# 输入一个数组，求出这个数组中的逆序对的总数 P。并将 P 对 1000000007 取模的结果输出。即输出 P % 1000000007。
# PS. 测试用例的数组长度可能超过 100k，防止超时。

class Solution:
    def InversePairs(self, data):
        p = self.inverse_pairs_count(data)
        return p % 1000000007

    # 使用循环版归并排序（递归版本容易超过 python 最大递归深度）
    def inverse_pairs_count(self, data):
        p = 0
        data = data[:]
        step = 1
        while step < len(data):
            for start in range(0, len(data) - step, step * 2):
                mid = start + step
                end = min(start + step * 2, len(data))
                p += self.inverse_pairs_combine(data, start, mid, end)
            step *= 2
        return p

    def inverse_pairs_combine(self, data, start, mid, end):
        p = 0
        l, r = start, mid
        tmp = []
        while l < mid and r < end:
            if data[l] > data[r]:
                tmp.append(data[r])
                r += 1
                p += mid - l
            else:
                tmp.append(data[l])
                l += 1
        if l < mid:
            tmp += data[l : mid]
        if r < end:
            tmp += data[r : end]
        data[start : end] = tmp
        return p