P8218 [Deep Intro 1. Example 1] Range Sum.

Given a sequence $a_1, a_2, \cdots, a_n$ consisting of $n$ positive integers and $m$ intervals $[l_i, r_i]$, find the sum of elements in each of the $m$ intervals.

The first line contains a positive integer $n$, representing the length of the sequence. The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$. The third line contains a positive integer $m$, representing the number of intervals. The next $m$ lines each contain two positive integers $l_i, r_i$, satisfying $1 \le l_i \le r_i \le n$.

Output $m$ lines. The $i$-th line contains a positive integer, representing the answer to the $i$-th query.

### Sample Explanation The sum of the $1$st to the $4$th numbers is $10$. The sum of the $2$nd to the $3$rd numbers is $5$. ### Constraints For $50\%$ of the testdata: $n, m \le 1000$. For $100\%$ of the testdata: $1 \le n, m \le 10^5$, $1 \le a_i \le 10^4$. Translated by ChatGPT 5