Consider an array of integers, . Let and be the respective maximum and minimum values in the inclusive range between index and .

Given , perform queries where each query consists of two integers, and . For each query, find and print the number of pairs that satisfy the following:

- .

**Input Format**

The first line contains two space-separated integers describing the respective values of (the size of array ) and (the number of queries).

The second line contains space-separated integers describing the respective values of .

Each line of the subsequent lines contains two space-separated integers describing the respective values of and for the query.

**Constraints**

- for

**Output Format**

Print lines where each line is the number of possible pairs for the query.

**Sample Input 0**

```
4 3
1 2 1 4
1 1
2 2
2 3
```

**Sample Output 0**

```
3
0
3
```

**Explanation 0**

The diagram below breaks down the possible pairs for each query on :

As you can see, the first query has pairs, the second has pairs, and the third has pairs.