← 返回题目列表

AtCoder · arc218_d

D. 我喜欢增加

中文机器翻译题面 查看原题

分数: 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