题目描述
一个研究团队正在研究象形文字序列的一些性质，他们将每个象形文字复杂程度表示成一个正整数，没有两个象形文字被表示的数一样。为了开展研究，他们采用了关于序列的如下概念。
对于一个给定长度为 $n$ 下标从 $1$ 开始的序列 $A$：
- $A$ 能被称为排列，当且仅当 $1,2,\cdots,n$ 分别在 $A$ 中有且仅有出现一次。
- 某个序列 $B$ 被称为是 $A$ 的子序列，当且仅当 $B$ 能够通过移除 $A$ 中的某些（也可能零个）元素而得到。
- $A$ 的区间 $[l,r]$ 是 $A_l,A_{l+1},\cdots,A_{r}$ 构成的序列。
研究人员想知道一个排列 $A$ 的区间 $[l_i,r_i]$ 的最长上升子序列的长度。
据说研究人员用了三天只会一个比较劣的做法。
输入格式
第一行输入两个正整数 $n,q$，表示排列大小和询问个数。
第二行输入 $n$ 个正整数 $a_i$，表示排列的元素。
接下来 $q$ 行每行输入两个正整数 $l_i,r_i$，表示查询的区间。
输出格式
输出第 $q$ 行，每行输出一个正整数，表示最长的上升子序列的长度。
样例一
input
5 5 1 5 2 4 3 1 5 2 4 3 3 1 4 2 5
output
3 2 1 3 2
限制与约定
对于所有数据，保证 $1\leq n\leq 10^5,1\leq q \leq 10^6,1 \leq a_i\leq n$。
本题有 $5$ 个子任务。只有该任务下测试点全部通过才能得到该子任务的分数。
| 子任务编号 | 子任务分数 | 特殊限制 |
|---|---|---|
| $1$ | $5$ | $r_i-l_i \leq 10$ |
| $2$ | $25$ | $n \leq 10000$ |
| $3$ | $30$ | $l_{i-1} \leq l_i，r_{i-1} \leq r_i$ |
| $4$ | $30$ | $a$ 在所有长度为 $n$ 的排列中等概率选取 |
| $5$ | $10$ | 无特殊限制 |