Count Even Numbers in Subarrays

You are given an array of integers and a series of queries. For each query, you must count the number of even numbers in the subarray specified by the indices l and r (1-indexed).

To solve this problem, you can preprocess the array to build a prefix sum array where each element at index i stores the number of even numbers in the subarray from the beginning of the array to index i. Mathematically, if we define the prefix sum array P as:

$$P[i] = \begin{cases} 1, & \text{if } arr[i] \text{ is even}\\0, & \text{otherwise} \end{cases} + P[i-1] \quad \text{for } i \ge 1, \quad P[0]=\begin{cases} 1, & arr[0] \text{ is even}\\0, & \text{otherwise} \end{cases}$$

Then for a query with bounds l and r, the answer is given by:

$$\text{answer} = \begin{cases} P[r-1], & \text{if } l=1\\ P[r-1] - P[l-2], & \text{if } l > 1 \end{cases}$$

Your task is to implement this functionality by reading the input from stdin and writing the results to stdout.

inputFormat

The input is given in the following format:

The first line contains an integer n (1 ≤ n ≤ 10^5), the size of the array.
The second line contains n integers, representing the array elements.
The third line contains an integer q (1 ≤ q ≤ 10^5), the number of queries.
Each of the next q lines contains two space-separated integers l and r (1 ≤ l ≤ r ≤ n), representing a query.

outputFormat

For each query, output a single integer on a new line representing the number of even numbers in the subarray from index l to r (inclusive).

## sample

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

1
2
2

</p>