Par impar

Pentru un șir $a_1, a_2, \dots, a_N$ de numere întregi vrei să aplici o secvență de operații astfel încât să obții un nou șir $b$, tot de lungime $N$. Inițial șirul $b$ este vid.

Într-o operație faci una dintre următoarele:

1. Alegi toate pozițiile pare ($2, 4, 6, \dots$) din $a$ și le adaugi în această ordine la finalul șirului $b$. După aceea ștergi toate aceste elemente din $a$. Această operație se poate aplica doar dacă șirul $a$ mai conține cel puțin $2$ elemente (observați că dacă șirul $a$ ar avea un singur element atunci aplicânda această operație, nu s-ar schimba nici $a$, nici $b$).
2. Alegi toate pozițiile impare ($1, 3, 5, \dots$) din $a$ și le adaugi în această ordine la finalul șirului $b$. După aceea ștergi toate aceste elemente din $a$. Această operație se poate aplica indiferent de lungimea șirului $a$.

Operațiile se repetă până ce șirul $a$ devine vid.

De exemplu, pentru șirul $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$, o secvență validă de operații este $1, 2, 2, 2$.

$a: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] \xrightarrow[]{1} [1, 3, 5, 7, 9] \xrightarrow[]{2} [3, 7] \xrightarrow[]{2} [7] \xrightarrow[]{2} []$.

$b: [] \xrightarrow[]{1} [2, 4, 6, 8, 10] \xrightarrow[]{2} [2, 4, 6, 8, 10, 1, 5, 9] \xrightarrow[]{2} [2, 4, 6, 8, 10, 1, 5, 9, 3] \xrightarrow[]{2} [2, 4, 6, 8, 10, 1, 5, 9, 3, 7]$.

Se observă că ultima operație, este obligatoriu de tipul $2$, deoarece șirul $a$ conținea un singur element (pe $7$).

Cerință

Se dă $N$, șirul $a$ și $Q$ întrebări de forma $L \ R$. Să se spună pentru fiecare întrebare în câte moduri putem aplica operațiile astfel încât $L \leq S_b \leq R$, unde $S_b$ este suma maximă a unei subsecvențe din $b$.

Date de intrare

Pe prima linie a fișierului parimpar.in se află numerele întregi $N, Q$ în ordinea aceasta.
Pe a doua linie se află șirul $a_1, a_2, \dots, a_N$.
Pentru fiecare $i$ de la $1$ la $Q$, pe linia $i + 2$ se află câte două numere, $L$ și $R$, reprezentând cea de a $i$-a întrebare.

Date de ieșire

În fișierul parimpar.out se vor afișa $Q$ linii. Pe linia $i$ se va afla un singur număr natural, reprezentând răspunsul la întrebarea $i$.

Restricții și precizări

• $1 \leq N, Q \leq 2 \cdot 10^5$;
• $-10^9 \leq a_i \leq 10^9$
• Subsecvențele vide se numără și ele, așadar subsecvența de sumă maximă a unui șir are valoarea cel puțin $0$.

Exemplu

parimpar.in

8 4
3 -4 5 8 -6 2 -11 7
0 15
17 17
2 100
17 21
Copy

parimpar.out

1
3
8
5
Copy

Explicație

Aplicând secvența de operații $2, 1, 2, 2$ obținem $b = [3, 5, -6, -11, 8, 7, -4, 2]$. $S_b = 8 + 7 = 15$. La prima întrebare, aceasta este singura secvență de operații validă.

Aplicând secvența de operații $1, 2, 1, 2$, obținem $b = [-4, 8, 2, 7, 3, -6, -11, 5]$. $S_b = 8 + 2 + 7 + 3 = 20$. Aceasta contribuie la ultimele două întrebări.