partition

Cerință

Fie $S$ un şir de $Q$ numere întregi. O subsecvenţă $[X, Y]$ a şirului $S$, $0 \leq X \leq Y \leq Q-1$, se defineşte ca o secvenţă de elemente consecutive $S_X, S_{X+1}, \dots, S_Y$. Costul unei subsecvenţe se defineşte ca fiind valoarea minimă a unui element din aceasta. O partiție a şirului $S$ se definește ca o împărţire a lui $S$ în subsecvenţe astfel încât fiecare element al şirului aparţine exact unei subsecvente. Daca partiția este formată din $k$ subsecvențe, scorul acesteia se definește ca fiind suma costurilor celor $k$ subsecvențe.

Se dă un șir $V$ de $N (1 \leq N \leq 200 \ 000)$ numere întregi, $-10^9 \leq V_i \leq 10^9$. Se cere să se răspundă, pentru $M$ întrebări de forma $X_i$, $Y_i$, care este maximul dintre scorurile tuturor partițiilor subsecvenței $[X_i, Y_i]$

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

Date de intrare

Fișierul de intrare partition.in are urmatoarea structură:

• linia $1$: $N \ M$, reprezentând lungimea sirului $V$, respectiv numărul de întrebări
• linia $2$: $V_0 \ V_1 \dots V_{N-1}$, cele $N$ elemente ale șirului $V$.
• linia $3 + i$ $(0 \leq i \leq M-1)$: $X_i \ Y_i$ reprezentând cele $M$ întrebari.

Date de ieșire

Fișierul de ieșire partition.out va conține $M$ linii, pe fiecare dintre acestea se va găsi un singur număr întreg, maximul dintre scorurile tuturor partițiilor subsecvenței $[X_i, Y_i]$.

Restricții și precizări

• $1 \leq N, M \leq 200 \ 000$;
• $-10^9 \leq V_i \leq 10^9$;
• Pentru teste în valoare de $6$ puncte, $1 \leq N, M \leq 50$
• Pentru teste în valoare de alte $7$ puncte, $1 \leq N \leq 400$, $1 \leq M \leq 16 \ 000$
• Pentru teste în valoare de alte $38$ puncte, $1 \leq N \leq 2 \ 000$
• Testele nu sunt cele din timpul concursului

Exemplu

partition.in

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

partition.out

2
1
-4

Explicație

Pentru primul exemplu, avem un șir format din $N = 7$ elemente și $M = 3$ întrebări.

O partiție optimă a subsecventei $[0, 6]$ este următoarea: $(3),(−2),(5),(−2, −4, 1, −2)$, iar scorul acesteia este $2$, dat de suma costurilor subsecvențelor $(3, -2, 5, -4)$.

O partiție optimă a subsecventei $[2, 4]$ este următoarea: $(5),(−2, −4)$, iar scorul acesteia este $1$, dat de suma costurilor subsecvențelor $(5, -4)$.

O partiție optimă a subsecventei $[4, 6]$ este următoarea: $(−4, 1, −2)$, iar scorul acesteia este $−4$, dat de suma costurilor subsecvențelor $(-4)$.