UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4904. [Ctsc2017]最长上升子序列

统计 下载数据

Description

猪小侠最近学习了最长上升子序列的相关知识。对于一个整数序列 A=(a1,a2,?,ak),定义A 的子序列为:从A 中
删除若干个元素后(允许不删,也允许将所有k 个元素都删除),剩下的元素按照原来的顺序所组成的序列。如果
这个子序列的元素从左到右严格递增,则称它为A 的一个上升子序列。其中包含元素数量最多的上升子序列称为A 
的最长上升子序列。例如,(2,4,5,6)和 (1,4,5,6)都是 (2,1,1,4,7,5,6)的最长上升子序列,长度都为 4。现在
猪小侠遇到了这样一个问题:给定一个序列 Bm=(b1,b2,?,bm),设C 是 Bm的子序列,且C 的最长上升子序列的长
度不超过k,则C 的长度最大能是多少?猪小侠觉得这个问题太简单了,缺乏挑战,他决定提出一个更难的问题。
于是他给了你这样一个序列 B=(b1,b2,…,bn),以及若干次询问。每次询问会给定两个整数m 和k,你需要对于B 
序列的前m 个元素构成的序列 Bm=(b1,b2,?,bm)和k 回答上述问题。

Input

第一行两个整数 n,q其中 n是序列B 的长度,q是询问次数。
第二行是空格隔开的 n个正整数 b1,b2,?,bn 
接下来 q行,其中第 i行包含两个整数 mi,ki,表示对 m=mi,k=ki 进行询问。
N<=50000

Output

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

Sample 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

Sample Output

4
6
5
8
7
11

Hint

Source