AT_arc218_d.I like Increasing

You are given a permutation $P=(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$.

For a sequence of integers $x=(x_1,x_2,\dots,x_k)$, define the score of $x$ as the number of indices $i$ satisfying $x_i < x_{i+1}$.

Process the following query $Q$ times.

• You are given positive integers $l$ and $r$ with $1 \le l \le r \le N$. For $X = (P_l,P_{l+1},\dots,P_r)$, solve the following problem.
  • Let $M$ be the maximum score of a non-empty subsequence of $X$. Find the minimum length of a non-empty subsequence of $X$ whose score equals $M$.

What is a subsequence? A subsequence of a sequence $A$ is a sequence obtained by removing zero or more elements from $A$ and arranging the remaining elements in their original order.

给你一个 $(1,2,\dots,N)$ 的排列 $P=(P_1,P_2,\dots,P_N)$。

对于一个整数序列 $x=(x_1,x_2,\dots,x_k)$，定义其得分为满足 $x_i < x_{i+1}$ 的下标 $i$ 的个数。

你需要处理 $Q$ 次如下查询：

• 给定满足 $1 \le l \le r \le N$ 的正整数 $l$ 和 $r$。令 $X = (P_l,P_{l+1},\dots,P_r)$，求解以下问题：
  • 设 $M$ 为 $X$ 的所有非空子序列中最大的得分。求 $X$ 中得分等于 $M$ 的非空子序列的最小长度。

什么是子序列？序列 $A$ 的子序列是指从 $A$ 中删除零个或多个元素后，将剩余元素按其在 $A$ 中的原始顺序排列所得到的序列。

The input is given from Standard Input in the following format:

$N$ $Q$
$P_1\ P_2\ \dots\ P_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

Each query is given in the following format:

$l\ r$

输入从标准输入中按以下格式给出：

$N$ $Q$
$P_1\ P_2\ \dots\ P_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

每个查询的格式如下：

$l\ r$

Output $Q$ lines. The $i$-th line should contain the answer to $\mathrm{query}_i$.

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

Sample 1 Explanation:
For the first query, $X = (2,1,4)$. The maximum score $M = 1$ is achieved by $(2,4),(1,4),(2,1,4)$. The minimum length among these is $2$, achieved by $(2,4),(1,4)$.

For the second query, $X = (4,6,3,5)$ and $M = 2$. $(4,6,3,5)$ achieves the minimum length $4$ among those with score $2$.

For the third query, $X = (1)$ and $M = 0$. $(1)$ achieves the minimum length $1$ with score $0$.

For the fourth query, $X = (2,1,4,6,3,5)$ and $M = 3$. $(2,4,6,3,5)$ achieves the minimum length $5$ with score $3$.

Constraints

• $1 \le N,Q \le 2 \times 10^5$
• $P$ is a permutation of $(1,2,\dots,N)$.
• $1 \le l \le r \le N$
• All input values are integers.

样例 1 解释：
对于第一个查询，$X = (2,1,4)$。最大 得分 $M = 1$ 可由子序列 $(2,4)$、$(1,4)$、$(2,1,4)$ 达到。其中长度最小者为 $2$，由 $(2,4)$ 和 $(1,4)$ 实现。

对于第二个查询，$X = (4,6,3,5)$，且 $M = 2$。子序列 $(4,6,3,5)$ 在所有 得分 为 $2$ 的子序列中具有最小长度 $4$。

对于第三个查询，$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$
• 所有输入值均为整数。