SecvCost

Se dă un șir $V$ de $N$ numere naturale distincte. O secvență $[X, Y]$ este formată din toate pozițiile consecutive dintre $X$ și $Y$ din șir. Se definește costul unei poziții $P$ ca fiind valoarea din șir de pe poziția $P$ înmulțită cu lungimea maximă a unei secvențe care conține poziția $P$ și a cărei valoare maximă se află tot pe poziția $P$.

Cerință

Se dau $M$ întrebări de forma: $X, Y$ – să se calculeze suma tuturor costurilor pozițiilor din secvența $[X, Y]$.
Atenție! Când se calculează costul unei poziții $P$ din $[X, Y]$, secvența de lungime maximă pe care valoarea $V_P$ este maximă se calculează în funcție de tot șirul, NU în funcție de secvența $[X, Y]$ (pentru clarificare urmăriți exemplul).

Date de intrare

Fișierul de intrare secvcost.in conține pe prima linie cele două numere $N$ și $M$, separate prin spațiu. Pe a doua linie se află $N$ numere naturale distincte reprezentând elementele șirului $V$. Pe următoarele $M$ linii se află perechi de valori $X, Y$ reprezentând întrebările la care trebuie să se răspundă.

Date de ieșire

Fișierul de ieșire secvcost.out va conține $M$ linii cu câte un număr pe fiecare linie reprezentând răspunsul la cele $M$ întrebări, în ordine.

Restricții și precizări

• Toate valorile din șir sunt mai mici sau egale decât $5 \ 000 \ 000$

Exemplul 1

secvcost.in

5 2
2 3 1 5 4
3 3
2 2

secvcost.out

1
9

Explicație

Pentru prima întrebare avem $V_3 = 1$ care este maxim pe secvența $[3, 3]$. Costul este $1 \cdot 1 = 1$. Pentru a doua întrebare avem $V_2 = 3$ care este maxim pe secvența $[1, 3]$. Costul este $3 \cdot 3 = 9$.

Exemplul 2

secvcost.in

5 3
2 3 1 5 4
1 3
5 5
4 4

secvcost.out

12
4
25

Explicație

$2 \cdot 1 + 3 \cdot 3 + 1 \cdot 1 = 12$
$4 \cdot 1 = 4$
$5 \cdot 5 = 25$

Exemplul 3

secvcost.in

10 10
10 30 29 39 34 32 3 6 7 9
6 7
1 7
6 10
1 5
7 9
4 7
3 7
5 6
3 7
6 10

secvcost.out

163
886
232
723
36
757
786
364
786
232