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

Poveste şi cerinţă...

_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~_]
 
*Important! Desi valorile elementelor sirului V nu sunt generate aleator, ordinea acestora în sir este aleatoare.*
 
h2. Detalii de implementare
 
Trebuie sa implementati urmatoarea functie :
std::vector<long long> find_partitions(std::vector<int> V, std::vector<int> X, std::vector<int> Y);

h2. Date de intrare