_Error 404: Poveste not found_

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ţa de elemente consecutive S[~X~], S[~X+1~],....,S[~Y~]. Costul unei subsecvenţe se defineşte 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