AT_arc218_d [ARC218D] I like Increasing

给定一个长度为 $N$ 的排列 $P = (P_1, P_2, \dots, P_N)$，其元素为 $1,2,\dots,N$ 的一个排列。 对于一个整数序列 $x=(x_1,x_2,\dots,x_k)$，定义该序列的 **得分** 为满足 $x_i < x_{i+1}$ 的下标 $i$ 的个数。 需要处理 $Q$ 次如下的查询： - 给定正整数 $l$ 和 $r$，满足 $1 \le l \le r \le N$，对于 $X = (P_l,P_{l+1},\dots,P_r)$，解决下列问题： - 设 $M$ 表示 $X$ 的所有非空子序列得分的最大值。求得分等于 $M$ 的所有非空子序列中，长度的最小值。 **子序列**的定义如下：对于一个序列 $A$，其子序列是通过从 $A$ 中去除零个或多个元素，并保持剩余元素的相对顺序得到的序列。

输入从标准输入读取，格式如下： > $N$ $Q$ > $P_1\ P_2\ \dots\ P_N$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 每个查询格式如下： > $l\ r$

输出 $Q$ 行，第 $i$ 行输出对应 $\mathrm{query}_i$ 的答案。

### 样例解释 1 对于第一组查询，$X = (2,1,4)$。最大得分 $M = 1$，能得到 $M$ 的子序列有 $(2,4),(1,4),(2,1,4)$。其中最小长度为 $2$，即 $(2,4)$ 或 $(1,4)$。 对于第二组查询，$X = (4,6,3,5)$，有 $M = 2$。$(4,6,3,5)$ 的子序列 $X$ 自身的得分为 $2$，长度为 $4$，这是得分为 $2$ 的最短子序列。 对于第三组查询，$X = (1)$，$M = 0$。子序列 $(1)$ 得分为 $0$，长度为 $1$。 对于第四组查询，$X = (2,1,4,6,3,5)$，有 $M = 3$，子序列 $(2,4,6,3,5)$ 得分为 $3$，长度为 $5$。 ### 数据范围 - $1 \le N, Q \le 2 \times 10^5$ - $P$ 是 $1,2,\dots,N$ 的一个排列。 - $1 \le l \le r \le N$ - 所有输入均为整数。 由 ChatGPT 5 翻译