题目描述

给定 $1\sim n$ 的排列 $p$，$q$ 次询问，每次查询区间 $[l,r]$ 内的最长上升子序列长度。

输入格式

第一行两个正整数 $n,q$。

第二行 $n$ 个正整数，表示排列 $p$。

之后 $q$ 行，每行两个正整数 $l,r$，表示一次询问。

输出格式

对于每次询问，输出对应的答案。

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

提示

对于所有数据，$1\leq n,q\leq10^5$，$1\leq l\leq r\leq n$。