题解 | 小红的子序列逆序对

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, x, val):
        while x <= self.n:
            self.tree[x] = (self.tree[x] + val) % MOD
            x += x & -x

    def query(self, x):
        res = 0
        while x > 0:
            res = (res + self.tree[x]) % MOD
            x -= x & -x
        return res


N = 100005
MOD = 10 ** 9 + 7

# Precompute powers of 2
f = [1] * N
for i in range(3, N):
    f[i] = (f[i - 1] * 2) % MOD


def solve():
    n = int(input())
    a = list(map(int, input().split()))

    bit = BIT(100000)
    ans = 0

    for i in range(n):
        # Count inversions for current element
        inversions = (bit.query(100000) - bit.query(a[i]) + MOD) % MOD
        ans = (ans + inversions) % MOD
        bit.update(a[i], 1)

    # Multiply result by 2^n
    ans = (ans * f[n]) % MOD
    print(ans)


if __name__ == "__main__":
    t = 1
    # t = int(input())  # Uncomment for multiple test cases
    for _ in range(t):
        solve()