猪小侠最近学习了最长上升子序列的相关知识。对于一个整数序列 $A=(a_1,a_2,\cdots ,a_k)$，定义 $A$ 的子序列为：从 $A$ 中删除若干个元素后（允许不删，也允许将所有 $k$ 个元素都删除），剩下的元素按照原来的顺序所组成的序列。如果这个子序列的元素从左到右严格递增，则称它为 $A$ 的一个上升子序列。其中包含元素数量最多的上升子序列称为 $A$ 的最长上升子序列。例如，$(2,4,5,6)$ 和 $(1,4,5,6)$ 都是 $(2,1,1,4,7,5,6)$ 的最长上升子序列，长度都为 $4$。

现在猪小侠遇到了这样一个问题：给定一个序列 $B_m=(b_1,b_2,\cdots ,b_m)$，设 $C$ 是 $B_m$ 的子序列，且 $C$ 的最长上升子序列的长度不超过 $k$，则 $C$ 的长度最大能是多少？

猪小侠觉得这个问题太简单了，缺乏挑战，他决定提出一个更难的问题。于是他给了你这样一个序列 $B=(b_1,b_2,\cdots ,b_n)$，以及若干次询问。每次询问会给定两个整数 $m$ 和 $k$，你需要对于 $B$ 序列的前 $m$ 个元素构成的序列 $B_m=(b_1,b_2,\cdots ,b_m)$ 和 $k$ 回答上述问题。

输入格式

第一行两个整数 $n,q$，其中 $n$ 是序列 B 的长度，$q$ 是询问次数。

第二行是空格隔开的 $n$ 个正整数 $b_1,b_2,\cdots ,b_n$。

接下来 $q$ 行，其中第 $i$ 行包含两个整数 $m_i,k_i$，表示对 $m=m_i,k=k_i$ 进行询问。

输出格式

输出共 $q$ 行，按顺序每行一个整数作为回答。

样例一

input

11 6
9 6 3 1 5 12 8 4 2 2 2
5 1
7 2
9 1
9 2
11 1
11 11

output

4
6
5
8
7
11

explanation

询问1：对于序列$(9,6,3,1,5)$，可以选取子序列$(9,6,3,1)$，它的最长上升子序列长度为$1$。

询问2：对于序列$(9,6,3,1,5,12,8)$，可以选取子序列$(9,6,3,1,12,8)$，它的最长上升子序列长度为$2$。

询问3：对于序列$(9,6,3,1,5,12,8,4,2)$，可以选取子序列$(9,6,5,4,2)$，它的最长上升子序列长度为$1$。

询问4：对于序列$(9,6,3,1,5,12,8,4,2)$，可以选取子序列$(9,6,3,1,12,8,4,2)$，它的最长上升子序列长度为$2$。

询问5：对于序列$(9,6,3,1,5,12,8,4,2,2,2)$，可以选取子序列$(9,6,5,4,2,2,2)$，它的最长上升子序列长度为$1$。

询问6：对于序列$(9,6,3,1,5,12,8,4,2,2,2)$，可以选取子序列$(9,6,3,1,5,12,8,4,2,2,2)$，它的最长上升子序列长度为$3$。

样例二

见样例数据下载。

限制与约定

对于 $100\mathrm{\%}$ 的数据，$1\le n\le 50000,1\le b_i\le 50000$，$1\le q\le 200000$，$1\le k_i\le m_i\le n$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载