## Task

Chimmy has an array of $N$ integers and $Q$ queries of the form $a \ b$, where for each query Chimmy wants to know, when traversing the subarray from position $a$ to position $b$, how many times the running maximum changes. Chimmy, not knowing how to program, asks for your help for $100$ points!

## Input data

The program reads from the keyboard the numbers $N$ and $Q$, after which it reads $N$ numbers representing the array.

The next $Q$ lines will contain two numbers $a$ and $b$, as described in the statement.

## Output data

The answer for each query will be displayed on a separate line.

## Restrictions and clarifications

- It is recommended to use fastio.
- $1 ≤ N ≤ 1 \ 000 \ 000$
- $1 ≤ Q ≤ 1 \ 000 \ 000$
- $1 ≤ a, b ≤ N$
- The numbers in the array can be represented on signed 32-bit integers.
- Traversals from $a$ to $b$ will not always be from left to right. For example, if $a = 5$ and $b = 3$, the indices will be traversed in the order $5, 4, 3$.

## Example

`stdin`

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

`stdout`

```
4
2
3
3
1
```

### Explanation

In the subarray $[1, 3, 5, 2, 8]$, the maximum changes $4$ times ($1$, $3$, $5$, $8$).

In the subarray $[3, 5, 2]$, the maximum changes $2$ times ($3$, $5$).

In the subarray $[4, 6, 1, 3, 5, 2, 8]$, the maximum changes $3$ times ($4$, $6$, $8$).

In the subarray $[2, 5, 3, 1, 6, 4]$, the maximum changes $3$ times ($2$, $5$, $6$) (the subarray $[6, 1]$ was traversed in reverse).

In the subarray $[5]$, the maximum only changes once ($5$).