Courses

動態規劃

GWP（最大递增子序列）

Module: GWP（最大递增子序列）

Problem

6 /6

水豚。缆车

Problem

<分区> Vasya 最近去过森林，因此决定在树上建造缆车。他希望路越长越好，但他记不清森林里树木的高度。幸运的是，他确信自己正确地记住了所有树的高度，也许其中一棵除外。

<分区>
已知森林由n棵树组成，n棵树排成一排，从左到右编号，编号从1到n。根据 Vasya 的说法，第 i 棵树的高度是 h_i。长度为 k 的缆车必须停在 k (1 <= k <= n) 棵树 i₁, i₂, ... 上。 . . , i_k (i₁ < i₂ < . . . < i_k), 这样它们的高度增加，即 h_i1 <; h_i2 < . . . < h_ik.

<分区> Petya 也在森林里，他有 q 个猜测 Vasya 到底错在哪里。他的第 i 个猜测由数字 a_i 和 b_i 给出，这意味着，在 Petya 看来，树的高度

<分区> 数字 a_i 实际上等于 b_i 。请注意，Petya 的假设是相互独立的。

<分区>
你的任务是针对 Petya 的每一个猜测，找出可以基于这些树建造的缆车的最大长度。

<分区> 请注意，在这个问题的框架内，Vasya 将其中支撑树的数量视为道路的长度。

<分区> 输入数据格式

<分区> 输入的第一行包含两个数字 n 和 m (1 <= n, m <= 400 000) —分别是森林中树木的数量和 Petya 的猜测数量。

<分区> 下一行包含 n 个整数 h_i (1 <= h_i <= 10⁹ ) —根据 Vasya 的建议调整树的高度。

<分区>
接下来的 m 行中的每一行包含两个整数 a_i 和 b_i (1 <= a_i <= n, 1 <= b_i <= 10⁹ ).

<分区>
输出格式 <分区> 对于 Petya 的每一个猜测，在单独的一行上打印一个数字——缆车的最大长度。

<正文> <分区> 注意 <分区> 让我们考虑第一个例子。 Petya 的第一个假设与 Vasya 的一致。 <分区> 根据他的第二个假设，树的高度是 (4, 2, 3, 4)，第三个是 (1, 2, 3, 3)，而根据第四个假设—— (1, 2, 3, 5).

time 3000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking