Given a sequence $a$ of length $n$ and $q$ queries, for each query, calculate the weight $f(a_{l\sim r})$ of the interval $[l, r]$.

The function $f(A)$ is defined as the number of non-empty rounds performed during $m$ rounds of operations, where $m$ is the length of the array $A$.

Specifically, in the $i$-th round (starting from $i=1$ to $m$), we check the relationship between $A_i$ and $A_t$ for all $t$ from $i+1$ to $m$. If $A_i < A_t$, we swap $A_i$ and $A_t$. A round is considered "non-empty" if at least one swap occurs during that round.

For example, for $f([1, 4, 2, 3])$, after each round, the array becomes $[4, 1, 2, 3]$, $[4, 3, 1, 2]$, $[4, 3, 2, 1]$, and $[4, 3, 2, 1]$. The first 3 rounds are non-empty, so $f([1, 4, 2, 3]) = 3$.

Note that the function $f$ does not cause any actual changes to the original array $a$; it is only used to calculate the weight.

Input

The first line contains two integers $n$ and $q$. The next line contains $n$ integers representing the array $a$. The next $q$ lines each contain two integers representing the interval $[l, r]$ for each query.

Output

Output $q$ lines, each containing an integer representing the answer to the corresponding query.

Examples

Input 1

5 5
2 2 1 3 3
1 2
1 5 
2 4
2 5
1 4

Output 1

0
4
2
3
2

Input 2

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

Output 2

1
0
1
0
1
0
1
2
2
1

Input 3

See the provided files.

Constraints

For all data, $1 \le n, q \le 10^6$ and $1 \le a_i \le n$.