Decode and Sum Queries

You are given an encoded sequence of integers. The encoded sequence is represented by pairs of integers, where the first integer in each pair specifies the number of times the second integer is repeated. Let the encoded sequence be E = [c₁, v₁, c₂, v₂, ..., c_k, v_k]. The decoded sequence D is constructed by repeating v_i exactly c_i times for every valid i.

After decoding, you will be given several queries. Each query consists of two indices L and R (using 0-based indexing). For each query, compute the sum of the subarray of D from index L to index R inclusive. In mathematical terms, for a query (L, R), you need to calculate:

$$S = \sum_{i=L}^{R}{D_i}$$

Example: If the encoded sequence is [2, 4, 3, 7], then the decoded sequence is [4, 4, 7, 7, 7]. For a query (0, 1), the answer is 4 + 4 = 8.

inputFormat

The input is given on stdin and has the following format:

1. An even integer m representing the number of integers in the encoded sequence.
2. m space-separated integers, which form the encoded sequence.
3. An integer q representing the number of queries.
4. q lines follow, each containing two space-separated integers L and R, representing a query.

outputFormat

For each query, output the sum of the decoded sequence elements from index L to R (inclusive) on a new line. The output is written to stdout.

## sample

4
2 4 3 7
3
0 1
2 4
0 4

8
21
29

</p>