Siclam

„Ce-i mai bun chiar decît ciorba?
Doar kebabul și shaorma”

După o noapte furtunoasă în clubul „La Regele”, Țil și Rose se îndreaptă spre Siclam să mănânce. Din păcate, după ce a aflat că în acea seară nu se mai servește meniul Cristi, Rose a decis că cea mai bună opțiune este un șnițăl cât roata la tractor. Cum Țil este școlit la universități înalte ale lumii, el cere $N$ șnițăle cât roata la tractor. Cum roțile la tractor nu sunt neapărat egale mereu, șnițălele pot avea diametre diferite. Cum Rose trebuie să-l hrănească și pe Lion, el va mânca din două în două șnițăle, iar Țil va mânca din trei în trei șnițăle. Povestea continuă printr-o noapte plină de peripeții. Pentru a nu vă plictisi cu detaliile, o să trecem la subiect.

Se dă un șir $a_1, \dots , a_N$ format din numere nenegative. Pe acest șir se va desfășura un joc între doi jucători, să îi numim $T$ și $R$, unde $T$ mută primul și jucătorii mută alternativ. Fiecare jucător are câte un pion plasat la o poziție din șirul $a$, cele două poziții fiind distincte. La o mutare, $T$ își poate muta pionul de la poziția $i$ la una din pozițiile $i ± 2$, iar $R$ de la poziția $i$ la una din pozițiile $i ± 3$. Jucătorii pot alege, de asemenea, să nu își mute pionul la o mutare, astfel sărindu-și tura. O poziție $1 ≤ i ≤ N$ se consideră capturată de un jucător dacă pionul jucătorului a fost la un moment în joc pe poziția $i$. O mutare a unui jucător este validă doar dacă poziția pe care ajunge pionul rămâne în intervalul $[1, N]$ și nu a fost deja capturată de celălalt jucător. Jocul se termină după ce s-au efectuat, în total, $10^{100}$ mutări.

La finalul jocului, scorul unui jucător este suma valorilor asociate pozițiile capturate de el. Câștigă jucătorul cu scorul cel mai mare, iar în caz de egalitate câștigă $R$. Vom presupune că ambii jucători joacă optim, adică dacă au o strategie care le garantează câștigul atunci o vor pune în aplicare.

Cerință

Se dau $Q$ interogări de forma $(l , r)$. Pentru fiecare interogare să se calculeze numărul de perechi $(i, j)$ cu $i ≠ j$ există astfel încât $l ≤ i, j ≤ r$ și ar câștiga $T$ dacă pionul său ar începe la poziția $i$ și pionul lui $R$ ar începe la poziția $j$. Atenție: se consideră atât $i < j$ cât și $i > j$.

Date de intrare

Pe prima linie a intrării se află numărul întreg $N$. Pe a doua linie a intrării se află $N$ numere nenegative $a_1, \dots , a_N$ reprezentând tabla de joc. Pe a treia linie a intrării se află numărul întreg $Q$. Pe următoarele $Q$ linii regăsim câte doi întregi $l, r$ reprezentând datele unei interogări.

Date de ieșire

Ieșirea va conține $Q$ linii, fiecare conținând răspunsul la câte o interogare, în ordinea de la intrare.

Restricții și precizări

• $3 \leq N \leq 500 \ 000$
• $1 \leq Q \leq 500 \ 000$
• $0 ≤ v_i ≤ 1 \ 000 \ 000 \ 000$ pentru $1 ≤ i ≤ N$

Exemple

stdin

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

stdout

27
12
1
8

Explicație

Pentru a treia interogare avem $l = 2, r = 3$. În acest caz, $T$ câstigă dacă pionul său începe la poziția $3$ și pionul lui $R$ începe la
poziția $2$.

Pentru a patra interogare avem $l = 4, r = 7$. În acest caz, $T$ câstigă dacă pozițiile inițiale ale pionilor $(t, c)$ fac parte din mulțimea $\{(4, 5), (5, 4), (4, 7), (7, 4), (5, 6), (6, 5), (6, 7), (7, 6)\}$.