Sum of Even Indexed Elements

You are given a list of n integers and q queries. For each query, you must compute the sum of the elements at even indices within a subarray specified by its start index l and end index r (inclusive).

Mathematically, for a query \( (l, r) \) and an array \( A[0 \ldots n-1] \), you need to calculate:

\( S = \sum_{\substack{i=l\\ i \equiv 0 \; (\bmod\;2)}}^{r} A[i] \)

Note that the condition \( i \equiv 0 \; (\bmod\;2) \) indicates that only the elements at even indices (0-indexed) should be summed.

inputFormat

The input is given in the following format:

1. The first line contains a single integer n (1 \(\leq n \leq 10^5\)) — the number of elements in the list.
2. The second line contains n space-separated integers, representing the elements of the list.
3. The third line contains an integer q (1 \(\leq q \leq 10^5\)) — the number of queries.
4. Each of the next q lines contains two integers l and r (0 \(\leq l \leq r \lt n\)), representing a query on the subarray from index l to r (inclusive).

outputFormat

For each query, output a single line containing the sum of the elements located at even indices in the subarray from index l to r (inclusive).

## sample

5
1 2 3 4 5
3
0 4
1 3
2 4

9
3
8

</p>