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

Limits: 4 sec., 512 MiB

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

Тобі задано алгоритм, який для заданого масиву \(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)\).

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

Input

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

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

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

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

Output

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

Constraints

\(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 балів: без додаткових обмежень.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1 2 3 4 2 1 4 2 4	0 6

Input (stdin) сopy	Output (stdout) сopy
5 4 7 4 7 4 1 1 5	-4

Notes

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

\[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\).