Description

Input

The first line contains two integers $n$ and $q$ ($1\leq n \leq 2 \cdot 10^5$; $1 \leq q \leq 10^6$) — the length of permutation $p$ and the number of queries.

The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$) — the permutation $p$.

Each of the next $q$ lines contains two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq n$) — the segment $[l_i,r_i]$ of this query.

Output

For each query, print one integer — the numbers of beautiful subsegments in the segment $[l_i,r_i]$.

8 3
1 3 5 2 4 7 6 8
1 3
1 1
1 8

2
0
10

10 10
6 1 3 2 5 8 4 10 7 9
1 8
1 10
1 2
1 4
2 4
5 8
4 10
4 7
8 10
5 9

17
25
1
5
2
0
4
1
0
0

Note

In the first example, for the first query, there are $2$ beautiful subsegments — $[1,2]$ and $[1,3]$.