Đếm số chẵn trong đoạn

Cho dãy số nguyên dương \(a_1, a_2, \dots, a_n\) và \(q\) câu hỏi. Mỗi câu hỏi gồm hai số \(l, r\): hãy đếm xem trong đoạn \(a_l, a_{l+1}, \dots, a_r\) có bao nhiêu số chẵn.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^9\)).
• Dòng thứ ba chứa số nguyên dương \(q\) (\(1 \le q \le 10^5\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le n\)).

Output

• In ra \(q\) dòng, dòng thứ \(j\) là số lượng số chẵn trong đoạn của câu hỏi thứ \(j\).

Subtask

• \(50\%\) số test: \(n, q \le 1000\).
• \(50\%\) số test: không có ràng buộc gì thêm.

Sample Input 1

6
2 7 4 4 9 10
3
1 6
2 2
3 5

Sample Output 1

4
0
2

Notes

• Đoạn \([1, 6]\) có các số chẵn \(2, 4, 4, 10\).
• Đoạn \([2, 2]\) chỉ có số \(7\).
• Đoạn \([3, 5]\) có các số chẵn \(4, 4\).