P2075 区间 LIS
题目描述
给定 $1\sim n$ 的排列 $p$，$q$ 次询问，每次查询区间 $[l,r]$ 内的最长上升子序列长度。
输入格式
第一行两个正整数 $n,q$。
第二行 $n$ 个正整数，表示排列 $p$。
之后 $q$ 行，每行两个正整数 $l,r$，表示一次询问。
输出格式
对于每次询问，输出对应的答案。
说明/提示
| 子任务编号 | $n$ | $q$ | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $10^3$ | $10^3$ | $20$ |
| $2$ | $10^3$ | $10^5$ | $30$ |
| $3$ | $10^5$ | $10^5$ | $50$ |
对于所有数据，$1\leq n,q\leq10^5$，$1\leq l\leq r\leq n$。