_Error 404: Poveste not found_
Fie S un sir de Q numere intregi. O subsecventa [X, Y] a sirului S , 0 ≤ X ≤ Y ≤ Q-1 , se defineste ca o secventa de elemente consecutive S[~X~], S[~X+1~],....,S[~Y~]. Costul unei subsecvente se defineste ca fiind valoarea minima a unui element din aceasta. O partitie a sirului S se defineste ca o impartire a lui S in subsecvente astfel incat fiecare element al sirului apartine exact unei subsecvente. Daca partitia este formata din k subsecvente, scorul acesteia scorul acesteie se defineste ca fiind suma costurilor celor k subsecvente.
Fie S un şir de Q numere întregi. O subsecvenţa [X, Y] a şirului S , 0 ≤ X ≤ Y ≤ Q-1 , se defineşte ca o secvenţă de elemente consecutive S[~X~], S[~X+1~],....,S[~Y~]. Costul unei subsecvenţe se defineşte ca fiind valoarea minimă a unui element din aceasta. O partitie a şirului S se defineste ca o împarţire a lui S in subsecvenţe astfel încât fiecare element al şirului aparţine exact unei subsecvente. Daca partitia este formată din k subsecvente, scorul acesteia se defineste ca fiind suma costurilor celor k subsecvente.
Se da un sir V de N (1 ≤ N ≤ 200 000) numere intregi , -10^9^ ≤ V[~i~] ≤ 10^9^. Se cere să se răspundă, pentru M întrebări de forma X[~i~] , Y[~i~] , care este maximul dintre scorurile tuturor partitiilor subsecventei [X[~i~], Y [~i~]]
*Important! Desi valorile elementelor sirului V nu sunt generate aleator, ordinea acestora în sir este aleatoare.*
*Important! Deşi valorile elementelor şirului V nu sunt generate aleator, ordinea acestora în sir este aleatoare.*
h2. Date de intrare
* linia 1: N M, reprezentand lungimea sirului V, respectiv numarul de intrebari
* linia 1: N M, reprezentând lungimea sirului V, respectiv numarul de intrebări
* linia 2: V[~0~] V[~1~] ... V[~N-1~], cele N elemente ale sirului V.
* linia 3 + i (0 ≤ i ≤ M-1): X[~i~] Y[~i~] reprezentand cele M intrebari.
