На складе контролёр проверяет партии деталей. Для каждой детали известен её номер. Деталь считается исправной для отчёта, если её номер чётный.

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

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

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

В первой строке задано число n — количество деталей.

Во второй строке записаны n целых чисел a_i — номера деталей.

В третьей строке задано число q — количество запросов.

В следующих q строках записаны по два целых числа l и r — границы выбранной партии деталей.

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

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

Ограничения

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

Примеры

Пример 1

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

5
0 1 -1 2 -2
6
1 1
2 2
3 3
4 4
5 5
1 1

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

1
0
0
1
1
1

Пример 2

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

8
-492673762 -496405053 764822338 111401587 774345046 -588077735 -972693438 959995351
7
3 3
5 6
1 3
5 8
1 5
3 8
1 7

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

1
1
2
2
3
3
4