分数: 700 点
问题陈述
给你一个排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).
对于整数序列 x=(x_1,x_2,\dots,x_k),定义 分数 $$$v$$$ 的 of x 作为索引的数量 i 满意 x_i < x_{i+1}.
处理以下查询 Q 次。
- 给你正整数 l 和 r 与 1 \le l \le r \le N。对于 X = (P_l,P_{l+1},\dots,P_r),解决以下问题。
- 让 M 是最大值 分数 $$$v$$$ 的 的非空子序列 X。求非空子序列的最小长度 X 谁 分数 $$$v$$$ 的 等于 M.
什么是子序列?
序列的子序列 A 是通过从其中删除零个或多个元素而获得的序列 A 并按原始顺序排列剩余元素。约束
- 1 \le N,Q \le 2 \times 10^5
- P 是一个排列 (1,2,\dots,N).
- 1 \le l \le r \le N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
6 4 2 1 4 6 3 5 1 3 3 6 2 2 1 6
示例输出 1
2 4 1 5
对于第一个查询, X = (2,1,4)。最大 分数 $$$v$$$ 的 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) 达到最小长度 4 在那些有 分数 $$$v$$$ 的 2.
对于第三个查询, X = (1) 和 M = 0. (1) 达到最小长度 1 与 分数 $$$v$$$ 的 0.
对于第四个查询, X = (2,1,4,6,3,5) 和 M = 3. (2,4,6,3,5) 达到最小长度 5 与 分数 $$$v$$$ 的 3.
示例输入 2
12 8 8 3 5 7 9 6 11 1 10 4 12 2 3 4 10 11 5 8 3 8 4 10 2 10 5 7 1 8
示例输出 2
2 2 2 4 5 7 2 5