== 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~_]

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.

*Important! Desi valorile elementelor sirului V nu sunt generate aleator, ordinea acestora în sir este aleatoare.*

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~]]

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);

*Important! Deşi valorile elementelor şirului V nu sunt generate aleator, ordinea acestora în sir este aleatoare.*

h2. Date de intrare

Fişierul de intrare $partition.in$ ...
 
h2. Date de ieşire

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

În fişierul de ieşire $partition.out$ ...
h2. Restricţii

h2. Punctare
 
|_. Subtask |_. Punctaj |_. Constrangeri|
|1       |6 puncte | 1 ≤ _N_ ≤ 50 ,  1 ≤ _M_ ≤ 50 |
|2       |7 puncte | 1 ≤ _N_ ≤ 400 , 1 ≤ _M_ ≤ 16000|
|3       |38 puncte | 1 ≤ _N_ ≤ 2000 , 1 ≤ _M_ ≤ 200 000|
|4       |49 puncte | 1 ≤ _N_ ≤ 200 000 ,  1 ≤ _M_ ≤ 200 000|

* $... ≤ ... ≤ ...$

h2. Exemplu

table(example). |_. partition.in |_. partition.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

table(example). |_. Ppartition.in |_. partition.out |
| 7 3
3 -2 5 -2 -4 1 -2
0 6
2 4
4 6
| 2
1
-4

|
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") ==