На участке установлены датчики, пронумерованные от 1 до n. Для каждого поста известно одно целое число — текущее показание датчика.

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

Иными словами, в сумму входят только показания на позициях 2, 4, 6, ..., если эти позиции принадлежат отрезку [l, r].

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

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

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

В третьей строке задано число 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

Ответы могут не помещаться в 32-битный целочисленный тип.

Примеры

Пример 1

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

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

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

0
10
10
17
7
7

Пример 2

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

6
-1 -2 -3 -4 -5 -6
7
1 6
2 5
2 6
3 3
4 4
5 6
6 6

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

-12
-6
-12
0
-4
-6
-6