5431. 「OOI 2016 Day 1」缆车

---

题目描述

题目译自 Open Olympiad in Informatics 2016 Day1 T1 「Канатная дорога / Zip-line」。

瓦西亚最近去了一趟森林，决定在树上建造一条缆车。他希望缆车尽可能长，但他对森林中树木高度的记忆有些模糊。幸运的是，他确信自己记得所有树木的高度，除了可能其中一棵有误。

已知森林中有 $n$ 棵树，按从左到右的顺序编号为 $1$ 到 $n$。根据瓦西亚的记忆，第 $i$ 棵树的高度为 $h_i$。一条长度为 $k$ 的缆车需要依托于 $k$ $(1 \leq k \leq n)$ 棵树，编号为 $i_1, i_2, \ldots, i_k$ $(i_1 < i_2 < \ldots < i_k)$，且这些树的高度必须是递增的，即 $h_{i_1} < h_{i_2} < \ldots < h_{i_k}$。

彼得也去过森林，他对瓦西亚的记忆提出了 $m$ 个假设。每个假设由一对数字 $a_i$ 和 $b_i$ 组成，表示彼得认为编号为 $a_i$ 的树的高度实际上是 $b_i$。需要注意的是，彼得的每个假设是相互独立的。

你的任务是，对于彼得的每个假设，计算在这种情况下可以建造的最长缆车的长度。

注意，在本题中，瓦西亚认为缆车的长度是指其依托的树木数量。

---

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 400000)$，分别表示森林中树木的数量和彼得的假设数量。

第二行包含 $n$ 个整数 $h_i$ $(1 \leq h_i \leq 10^{9})$，表示瓦西亚记忆中每棵树的高度。

接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$ $(1 \leq a_i \leq n, 1 \leq b_i \leq 10^{9})$，描述彼得的每个假设。

---

输出格式

对于彼得的每个假设，在单独的一行中输出一个整数，即在该假设下可以建造的最长缆车的长度。

---

样例 1

输入

4 4
1 2 3 4
1 1
1 4
4 3
4 5

输出

4
3
3
4

以第一个样例为例：

• 彼得的第一个假设与瓦西亚的记忆一致。
• 根据彼得的第二个假设，树木高度为 $(4, 2, 3, 4)$。
• 根据第三个假设，树木高度为 $(1, 2, 3, 3)$。
• 根据第四个假设，树木高度为 $(1, 2, 3, 5)$。

---

样例 2

输入

4 2
1 3 2 6
3 5
2 4

输出

4
3

---

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	测试点编号	分值	附加限制	备注
1	$3 \sim 32$	10	$n \leq 15$，$m \leq 15$，$h_i, b_i \leq 100$
2	$33 \sim 51$		$n \leq 500$，$m \leq 500$，$h_i, b_i \leq 500$
3	$52 \sim 70$	20	$n \leq 2000$，$m \leq 3000$，$h_i, b_i \leq 100000$
4	$71 \sim 89$		$n \leq 10000$，$m \leq 20000$，$h_i, b_i \leq 100000$
5	--		$n \leq 75000$，$m \leq 75000$
6				子任务 6 的测试点独立评分，每个测试点 1 分，且只有在通过前置子任务所有测试点后才会进行评测。