For each \(A_j\), consider how many times \(A_j\) contributes to the sum \(\displaystyle\sum_{l = L_i}^{R_i}\sum_{r = l}^{R_i}\sum_{j = l}^{r} A_j\).

If \(j < L_i\) or \(R_i < j\), then \(A_j\) does not contribute, so we only consider \(j\) with \(L_i \leq j \leq R_i\).

\(A_j\) is added once each when \(l \leq j \leq r\), so the number of times \(A_j\) contributes to the sum equals the number of integer pairs \((l, r)\) with \(L_i \leq l \leq j \leq r \leq R_i\).

There are \((j - L_i + 1)\) integers satisfying \(L_i \leq l \leq j\), and \((R_i - j + 1)\) integers satisfying \(j \leq r \leq R_i\), so the count of such pairs is \((j - L_i + 1)(R_i - j + 1)\).

Thus, the sought sum can be represented as \(\displaystyle\sum_{j = L_i}^{R_i} (j - L_i + 1)(R_i - j + 1)A_j\), which expands to \(\displaystyle\sum_{j = L_i}^{R_i} -j^2A_j + (L_i + R_i)jA_j + (-L_i + 1)(R_i + 1)A_j\).

This expression above to process one query in \(O(N)\) time.

To support \(Q\) queries, we precalculate the cumulative sums of \(j^2A_j, jA_j, A_j\), compute segment sums, multiple coefficients, and take the sum.