Pracsiu Dan (dnprx) Se dă un șir cu N elemente ce conține numerele naturale de la 1 la K, în această ordine, acestea putând fi separate de elemente egale cu 0. De exemplu, pentru N = 9, șirul poate fi 0, 1, 2, 3, 0, 0, 4, 0, 5. Acest șir poate fi completat succesiv cu câte un element după următoarea regulă: dacă printre ultimele N elemente din șir se află un număr impar de elemente nenule, atunci elementul care se adaugă este succesorul celui mai mare element nenul din șir, în caz contrar se va adăuga elementul 0. Pentru exemplul anterior, după adăugarea a încă 4 elemente, șirul va deveni 0, 1, 2, 3, 0, 0, 4, 0, 5, 6, 0, 7, 8.
Cerința
Să se răspundă la Q întrebări de forma: pentru două numere date l și r, care este valoarea sumei elementelor din șir de la indicele l la indicele r, inclusiv acestea?
Date de intrare
Pe prima linie a intrării standard se află numerele N și Q, pe a doua linie cele N elemente ale șirului dat, iar pe următoarele Q linii câte două numere reprezentând valorile lui l și r.
Date de ieșire
Se vor afișa la ecran, pe linii diferite, răspunsurile la cele Q întrebări.
Restricții și precizări
1 ≤ N, Q ≤ 100.0001 ≤ l ≤ r ≤ 2.000.000.000
Exemplul 1:
Intrare
9 2 0 1 2 3 0 0 4 0 5 1 4 7 13
Ieșire
6 30
Explicație
Avem N = 9 iar șirul este format cu elementele 0, 1, 2, 3, 0, 0, 4, 0, 5. Cum printre acestea se află 5 elemente nenule, deducem K = 5. Având un număr impar de elemente nenule printre ultimele 9 elemente din șir deducem că următorul element din șir este 6 (succesorul lui 5). Acum șirul este 0, 1, 2, 3, 0, 0, 4, 0, 5, 6, iar ultimele 9 elemente din șir sunt 1, 2, 3, 0, 0, 4, 0, 5, 6. Printre acestea avem un număr par de elemente nenule, deci următorul element din șir va fi 0. Șirul devine: 0, 1, 2, 3, 0, 0, 4, 0, 5, 6, 0. Ultimele 9 elemente din șir sunt 2, 3, 0, 0, 4, 0, 5, 6, 0, printre care avem un număr impar de elemente nenule, deci următorul element din șir va fi 7 (succesorul lui 6).
Elementele cuprinse între indicii 1 și 4 (inclusiv) sunt 0, 1, 2, 3 și suma lor este 6, iar elementele cuprinse între indicii 7 și 13 (inclusiv) sunt 4, 0, 5, 6, 0, 7, 8 și suma lor este 30.
Exemplul 2:
Intrare
3 2 1 2 3 1 5 3 8
Ieșire
15 33
Explicație
Șirul generat va fi 1, 2, 3, 4, 5, 6, 7, ... . Suma elementelor cuprinse între indicii 1 și 5 este 1 + 2 + 3 + 4 + 5 = 15, iar suma elementelor cuprinse între indicii 3 și 8 este 3 + 4 + ... + 8 = 33.