E - LEQ https://atcoder.jp/contests/abc221/tasks/abc221_e

abc221_e.py

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

    def sum(self, a):
        res = 0
        i = a - 1
        while i >= 0:
            res += self.bit[i]
            i = (i & (i + 1)) - 1
        return res

    def add(self, a, x):
        i = a
        while i < len(self.bit):
            self.bit[i] += x
            i |= i + 1


MOD = 998244353
N = int(input())
A = list(map(int, input().split()))

# 座標圧縮を行う
xs = sorted(set(A))
mp = {x: i for i, x in enumerate(xs)}
A = [mp[x] for x in A]

bit = BIT(max(A) + 1)
inv2 = pow(2, MOD - 2, MOD)  # 2 の逆元
ans = 0

for y in range(N):
    s = bit.sum(A[y] + 1)
    if y >= 1:
        ans = (ans + pow(2, y - 1, MOD) * s) % MOD
    bit.add(A[y], pow(inv2, y, MOD))

print(ans)