Lista de probleme 2

Giovani, sătul să piardă atât de mult la șah mutând pionii din fața regelui, incearcă să se orienteze spre alte activități și se înscrie la concursul anual de alergare dintre satul său natal, Păpucești și satul rival, Băbana. Competiția constă în a alerga cea mai mare distanță într-un anumit timp T fixat, cronometrat de comisia sătenilor. Pentru a face asta, comisia sătenilor dispune de un cronometru care pornește de la T. Odată activat, cronometrul va scădea cu câte o unitate de timp. Considerăm că la fiecare decrementare a cronometrului Giovani parcurge o unitate de lungime. Cum nu este nici un mare sportiv, Giovani îi cere ajutorul prietenului său, hackerul Cosminel. Cosminel îi spune că poate opri cronometrul comisiei, dar doar la anumite intervale de timp [li, ri], nu neapărat disjuncte, pentru a nu ridica suspiciuni. Afișați distanța cea mai mare pe care o poate parcurge Giovani până când cronometrul ajunge la 0 considerând că acesta poate trage de timp până la orice moment de pornire al cronometrului (număr natural) și că timpul începe de la momentul 1.

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. 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?