期待値の線形性を用いると、\(A_i\) 円支給される確率が各 \(i\) について求まればよいです。

更新された \(x\) を順に並べた列 \(v\) を考えます。求めたい確率は、\(v\) の中に \(i\) が含まれるような列全てに対する、その列が現れる確率の総和です。ここで、\(v\) の \(i\) より大きい要素は関係ないことに注意すると、手順中に \(v\) の末尾が \(i\) になる確率の総和が求まればよいです。

\(v\) の長さを全探索することを考えると、求める確率として以下の式を得ます。

\[\sum _{k=1}^{k=i} \binom{i-1}{k-1}\frac{1}{N^k} =\frac{1}{N}\Big(1+\frac{1}{N}\Big)^{i-1}\]

\((1+\frac{1}{n})^{j}\) を \(j=0,1,\ldots,N-1\) について列挙するのは \(\mathrm{O}(N)\) で出来るので、この問題を \(\mathrm{O}(N)\) で解くことができました。

なお、求める確率は式変形なしでより簡単に導出することもできます。\(j=1,2,\ldots,i-1\) について \(v\) に追加するかしないかを決めることを考えると、追加する場合は \(\frac{1}{N}\) 倍が付き 、追加しない場合は何も起こらないので結局同じ式が導かれます。

実装例(Python):

mod, n = 998244353, int(input())
a = list(map(int, input().split()))
p, q, res = pow(n, mod - 2, mod), 1 + pow(n, mod - 2, mod), 0
for v in a:
    res = (res + p * v) % mod
    p = (p * q) % mod
print(res)