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

Poveste şi cerinţă...

_Error 404: Poveste not found_

h2. Date de intrare

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

Fişierul de intrare $partition.in$ ...

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

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