Running Max

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$).