Контролёр проверяет партию деталей. У каждой детали есть целочисленный код. Деталь считается исправной, если её код чётный.

Дана последовательность из n кодов деталей и q запросов. В каждом запросе заданы числа l и r — границы выбранной подряд части партии, нумерация деталей ведётся с единицы.

Для каждого запроса определите, сколько исправных деталей находится на отрезке от l до r включительно.

Входные данные

Первая строка содержит целое число n — количество деталей в партии (1 <= n <= 2*10^5).

Во второй строке содержатся n целых чисел a_i — коды деталей (-10^9 <= a_i <= 10^9).

В третьей строке содержится целое число q — количество запросов (1 <= q <= 2*10^5).

В следующих q строках содержатся по два целых числа l и r (1 <= l <= r <= n) — границы выбранной части партии.

Выходные данные

Для каждого запроса выведите одно число — количество исправных деталей на соответствующем отрезке.

Ограничения

• 1 <= n <= 2*10^5
• -10^9 <= a_i <= 10^9
• 1 <= q <= 2*10^5
• 1 <= l <= r <= n

Примеры

Пример 1

Входные данные

5
-2 -1 0 1 2
7
1 1
2 2
3 3
1 5
2 4
4 5
5 5

Выходные данные

1
0
1
3
1
1
1

Пример 2

Входные данные

6
2 4 6 8 10 12
8
1 6
1 1
6 6
2 5
3 4
4 4
1 3
5 6

Выходные данные

6
1
1
4
2
1
3
2