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

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

*linia 1: N M, reprezentand lungimea sirului V, respectiv numarul de intrebari
*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.

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

h2. Punctare

h2. Exemplu

table(example). |_. Intrare |_. Iesire |

table(example). |_. Ppartition.in |_. partition.out |

| 7 3
3 -2 5 -2 -4 1 -2
0 6