静态区间最长递增子序列查询（Static Range LIS Query）

问题描述

给定一个排列 $P$，即 $\{0,1,\dots,N-1\}$ 的一个重排。
处理 $Q$ 个查询：对每个查询 l r，输出子数组 $(P_l, P_{l+1}, \dots, P_{r-1})$ 的最长递增子序列（LIS）的长度。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $P$ 是 $\{0,1,\dots,N-1\}$ 的一个排列
• $0 \leq l < r \leq N$

输入

$N\ Q$
$P_0\ P_1\ \cdots\ P_{N-1}$
$l_0\ r_0$
$l_1\ r_1$
:
$l_{Q-1}\ r_{Q-1}$

4 3
0 2 1 3
0 2
0 4
1 3

2
3
1