A research team is studying certain properties of sequences of hieroglyphs. They represent the complexity of each hieroglyph as a positive integer, such that no two hieroglyphs are assigned the same number. To conduct their research, they have adopted the following concepts regarding sequences.

For a given sequence $A$ of length $n$ with 1-based indexing:

1. $A$ is called a permutation if and only if $1, 2, \dots, n$ each appear exactly once in $A$.
2. A sequence $B$ is called a subsequence of $A$ if and only if $B$ can be obtained by removing zero or more elements from $A$.
3. The interval $[l, r]$ of $A$ is the sequence formed by $A_l, A_{l+1}, \dots, A_r$.

The researchers want to know the length of the longest increasing subsequence of the interval $[l_i, r_i]$ of a permutation $A$.

It is said that the researchers spent three days and only came up with a suboptimal approach.

Input

The first line contains two positive integers $n$ and $q$, representing the size of the permutation and the number of queries, respectively.

The second line contains $n$ positive integers $a_i$, representing the elements of the permutation.

The next $q$ lines each contain two positive integers $l_i$ and $r_i$, representing the query interval.

Output

Output $q$ lines, each containing a single positive integer representing the length of the longest increasing subsequence.

Examples

Input 1

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

Output 1

3
2
1
3
2

Constraints

For all data, it is guaranteed that $1 \leq n \leq 10^5$, $1 \leq q \leq 10^6$, and $1 \leq a_i \leq n$.

This problem has 5 subtasks. You will receive points for a subtask only if all test cases within that subtask are passed.