Оптимізація алгоритму

Обмеження: 4 сек., 512 МіБ

Школяре, ти вмієш оптимізовувати алгоритми?

Тобі задано алгоритм, який для заданого масиву $a$ з $n$ цілих чисел обчислює на проміжку $a[l \dots r]$ деяке значення.

Ось псевдокод функції $f$, яка реалізовує алгоритм:

У циклі for змінні $i$ та $j$ перебирають значення від $l$ до $r$ включно. У псевдокоді умова $(i+j) \% 2 = 0$ перевіряє, чи $(i+j)$ — парне.

Цей алгоритм написаний неоптимально. Твоє завдання — оптимізувати його.

Тобі заданий масив $a$ з $n$ цілих чисел.

Ти повинен опрацювати таких $q$ запитів.

• $l\ r$ — обчислити значення функції $f(n, a, l, r)$.

Зауваж, що якщо ти реалізуєш алгоритм так, як у псевдокоді, ти не набереш повний бал — тобі потрібно реалізувати його оптимально.

Вхідні дані

У першому рядку записано ціле число $n$ — кількість елементів у масиві.

У другому рядку задано $n$ цілих чисел $a_i$ — елементи масиву.

У третьому рядку задано ціле число $q$ — кількість запитів.

У наступних $q$ рядках задано по два цілі числа $l$, $r$ — межі проміжку в запиті.

Вихідні дані

У $q$ рядках виведи відповіді на всі запити.

Обмеження

$1 \le n, q \le 3 \cdot 10^5$,

$1 \le l_i \le r_i \le n$,

$1 \le a_i \le 10^9$.

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 7 балів: $q = 1$, $l_i = 1, r_i = n$, $n$ — парне,

• 13 балів: $q = 1$, $l_i = 1, r_i = n$, $n \le 3 \cdot 10^3$, $a_i \le 10^3$,

• 10 балів: $q = 1$, $l_i = 1, r_i = n$, $n \le 3 \cdot 10^3$, $a_i \le 10^9$,

• 26 балів: $q = 1$, $l_i = 1, r_i = n$, $n \le 3 \cdot 10^5$, $a_i \le 10^3$,

• 20 балів: $q = 1$, $l_i = 1, r_i = n$, $n \le 3 \cdot 10^5$, $a_i \le 10^9$,

• 5 балів: $q = 1$, $n \le 3 \cdot 10^5$, $a_i \le 10^9$,

• 17 балів: без додаткових обмежень.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 2 3 4 2 1 4 2 4	0 6

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 4 7 4 7 4 1 1 5	-4

Примітки

Формула, яку реалізовує алгоритм:

$$s = \sum_{i = l}^{r} \sum_{j = l}^{r} (-1)^{i + j} \cdot (a_i + a_j).$$

Перший приклад:

$f(n, a[1 \dots n], 1, 4) = 2 - 3 + 4 - 5 - 3 + 4 - 5 + 6 + 4 - 5 + 6 - 7 - 5 + 6 - 7 + 8 = 0$,

$f(n, a[1 \dots n], 2, 4) = 4 - 5 + 6 - 5 + 6 - 7 + 6 - 7 + 8 = 6$.