== include(page="template/taskheader" task_id="partition") ==
_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.
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~_]

h3. Explicaţie

...

Pentru primul exemplu, avem un sir format din N = 7 elemente si M = 3 întrebări.
O partitie optimă a subsecventei [0, 6] este următoarea: (3),(−2),(5),(−2, −4, 1, −2), iar scorul acesteia este 2, dat de suma costurilor subsecventelor (elementele afisate îngrosat).
 
O partitie optimă a subsecventei [2, 4] este următoarea: (5),(−2, −4), iar scorul acesteia este 1, dat de suma costurilor subsecventelor (elementele afisate îngrosat).
 
O partitie optimă a subsecventei [4, 6] este următoarea: (−4, 1, −2), iar scorul acesteia este −4, dat de suma costurilor subsecventelor (elementele afisate îngrosat).
 

== include(page="template/taskfooter" task_id="partition") ==