XYQueries10

Cerință

Se dă un șir $A$ cu $N$ elemente. Definim $\min(i,j)$ ca fiind valoarea minimă din subsecvența $[i,j]$ a șirului $A$. Analog, definim $\max(i,j)$ ca fiind valoarea maximă din subsecvența $[i,j]$ a șirului $A$. Se dau și $Q$ întrebări de forma $(X_i,Y_i)$ cu semnificația "câte subsecvențe $[l,r]$ au $\min(l,r)=X_i$ și $\max(l,r)=Y_i$?".

Testele pentru această problemă sunt generate aleator.

Date de intrare

Pe prima linie se află numerele $N$ și $Q$. Următoarea linie conține elementele $A_1,A_2, \dots, A_N$.
Pe fiecare din următoarele $Q$ linii se află două numere $X_i$ și $Y_i$.

Date de ieșire

Se vor afișa $Q$ linii, unde a $i$-a linie conține răspunsul la cea de a $i$-a întrebare.

Restricții și precizări

• $1 \leq N, Q \leq 10^5$
• $1 \leq A_{i} \leq N, \forall\ i \in \{1, 2, \dots, N\}$
• Testele pentru această problemă sunt generate aleator.

Exemplul 1

stdin

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

stdout

2
5
1
2
2

Exemplul 2

stdin

15 10
7 9 2 13 12 13 11 13 13 13 10 5 13 7 2
5 13
7 13
11 13
5 10
7 13
2 9
7 9
2 9
11 13
11 13

stdout

25
1
15
1
1
2
1
2
15
15