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)。