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ța

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
• Pentru 25% din teste N, M ≤ 500
• Pentru alte 25% din teste N, M ≤ 10.000
• Pentru restul de 50% din teste N, M ≤ 200.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 * 1 = 1. Pentru a doua întrebare avem V[2] = 3 care este maxim pe secvența [1, 3]. Costul este 3 * 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*1 + 3*3 + 1*1 = 12
4*1 = 4
5*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