XYQueries

Task

You are given an array $A$ with $N$ integers. Let $\min(i, j)$ be the minimum value in the subarray $A_i, A_{i+1}, \dots, A_j$, and $\max(i, j)$ the maximum value in the subarray $A_i, A_{i+1}, \dots, A_j$. You are also given $Q$ queries, for the $i^{th}$ query you are required to count the number of pairs $(l, r)$, $1 \leq l \leq r \leq N$ where $\min(l, r) = X_i$ and $\max(l, r) = Y_i$.

Input data

The first line of the input contains two integers $N$ and $Q$. The second line contains $N$ integers, $A_1, A_2, \dots, A_N$. The next $Q$ lines describe the queries, the $i^{th}$ of them contains two integers $X_i, Y_i$.

Output data

The output will consist of $Q$ lines, the $i^{th}$ line containing the answer to the $i^{th}$ query.

Constraints and clarifications

• $1 \leq N , Q \leq 10^{5}$
• $1 \leq A_i \leq N , \forall \ i \in \{1, 2, \dots, N \}$

Example 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

Example 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