← 返回题目列表

Codeforces · 650/D

D. 滑索

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

Vasya 决定在附近森林的树木上建造一条滑索。他希望队伍尽可能长,但他不记得森林中所有树木的确切高度。他确信自己记得所有树的正确高度,可能除了其中一棵树之外。

已知森林由n棵树组成,n棵树排成一排,从左到右编号为1到n的整数。根据 Vasya 的说法,第 i 棵树的高度等于 hi。长度为 k 的滑索应悬挂在 k (1 ≤ k ≤ n) 棵树 i1, i2, ..., ik (i1 < i2 < ... < ik) 上,使得它们的高度形成递增序列,即 hi1 < hi2 < ... < hik。

Petya 曾与 Vasya 一起在这片森林中,现在他对 Vasya 序列 h 中的错误有 q 个假设。他的第 i 个假设由两个整数 ai 和 bi 组成,这表明根据 Petya 的说法,编号为 ai 的树的高度实际上等于 bi。请注意,Petya 的假设是相互独立的。

你的任务是找到在每个 q 假设下可以在树上建造的滑索的最大长度。

在此问题中,滑索的长度被认为等于形成该滑索的树木数量。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 400 000)——分别是森林中树木的数量和 Petya 假设的数量。

下面一行包含 n 个整数 hi (1 ≤ hi ≤ 109) — 根据 Vasya 的树高。

以下 m 行每行包含两个整数 ai 和 bi (1 ≤ ai ≤ n, 1 ≤ bi ≤ 109)。

输出

对于 Petya 的每一个假设,都会输出一个整数,表示在该假设下可以构建的滑索的最大长度。

示例

输入 #1

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

输出 #1

4
3
3
4

输入 #2

4 2
1 3 2 6
3 5
2 4

输出 #2

4
3

注意

考虑第一个样本。第一个假设其实和瓦夏记忆中的身高是吻合的。在第二个假设中,树的高度是 (4, 2, 3, 4),在第三个假设中,树的高度是 (1, 2, 3, 3),在第四个假设中,树的高度是 (1, 2, 3, 5)。