Description

Given a permutation $p$ of $1\sim n$, there are $q$ queries. Each query asks for the length of the longest increasing subsequence within the interval $[l,r]$.

Input Format

The first line contains two positive integers $n,q$. The second line contains $n$ positive integers, representing the permutation $p$. Then $q$ lines follow, each containing two positive integers $l,r$, representing a query.

Output Format

For each query, output the corresponding answer.

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

3
2
2

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

4
3
3
3
3
4
4
2
1
2

Hint

For all testdata, $1\leq n,q\leq10^5$, $1\leq l\leq r\leq n$.

Translated by ChatGPT 5