For an integer \(n\), let \(\displaystyle H_n = \sum_{k=1}^n\frac1k\).

Solution \(1\)

For \(n=0,1,\ldots,N\), let \(\displaystyle B_n=\sum_{k=1}^n A_k\) (cumulative sums). Then \(\displaystyle f(l,r)=\frac{B_r-B_{l-1}}{r-l+1}\).

Therefore, the sought value can be transformed as follows:

\[ \begin{aligned} &\phantom{=}\sum_{1\le l\le r\le N} f(l,r)\\ &=\sum_{1\le l\le r\le N}\frac{B_r-B_{l-1}}{r-l+1}\\ &=\sum_{r=1}^N\sum_{l=1}^r\frac{B_r}{r-l+1}-\sum_{l=1}^N\sum_{r=l}^N\frac{B_{l-1}}{r-l+1}\\ &=\sum_{r=1}^N H_rB_r - \sum_{l=1}^N H_{N-l+1}B_{l-1}\\ &=\sum_{i=0}^N (H_i-H_{N-i})B_i \end{aligned} \]

Hence, the answer can be found by precalculating \(H_i\) and \(B_i\).

Sample code (Python3)

n = int(input())
a = list(map(int, input().split()))
MOD = 998244353
b = [0] * (n + 1)
for i in range(n):
    b[i + 1] = (b[i] + a[i]) % MOD
h = [0] * (n + 1)
for i in range(1, n + 1):
    h[i] = (h[i - 1] + pow(i, MOD - 2, MOD)) % MOD
ans = 0
for i in range(n + 1):
    ans += b[i] * (h[i] - h[n - i])
    ans %= MOD
print(ans)

Solution \(2\)

The sought value can be transformed as follows:

\[ \begin{aligned} &\phantom{=}\sum_{1\le l\le r\le N} f(l,r)\\ &=\sum_{1\le l\le r\le N}\sum_{i=l}^r\frac{A_i}{r-l+1}\\ &=\sum_{1\le l\le i\le r \le N}\frac{A_i}{r-l+1}\\ &=\sum_{i=1}^{N}A_i\sum_{l=1}^i \sum_{r=i}^{N}\frac1{r-l+1}\\ &=\sum_{i=1}^{N}A_i\sum_{l=1}^i (H_{N-l+1}-H_{i-l})\\ &=\sum_{i=1}^{N}A_i\sum_{j=0}^{i-1} (H_{N-j}-H_{j}) \end{aligned} \]

Since \(\displaystyle \sum_{j=0}^{i-1} (H_{N-j}-H_{j})\) can be computed in ascending order of \(i\), the answer can be obtained based on this equation too.

Sample code (Python3)

n = int(input())
a = list(map(int, input().split()))
MOD = 998244353
h = [0] * (n + 1)
for i in range(1, n + 1):
    h[i] = (h[i - 1] + pow(i, MOD - 2, MOD)) % MOD
ans = 0
res = 0
for i in range(n):
    res += h[n - i] - h[i]
    res %= MOD
    ans += a[i] * res
    ans %= MOD
print(ans)