#2265. 「CTSC2017」最长上升子序列

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

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

输入格式

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

输出格式

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

样例

样例输入

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

样例输出

4
6
5
8
7
11

样例解释

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

数据范围与提示

测试点 n n 约束
1 50000 \leq 50000 ki=1 k_i = 1
2 300 \leq 300 ki2 k_i \leq 2
3 3000 \leq 3000
4 50000 \leq 50000 bi5 b_i \leq 5
5 bi8 b_i \leq 8
6 100 \leq 100 mi=n m_i = n
7
8 800 \leq 800 mi=n,ki10 m_i = n, k_i \leq 10
9 1500 \leq 1500
10 10000 \leq 10000 mi=n,ki30 m_i = n, k_i \leq 30
11 15000 \leq 15000 mi=n,ki40 m_i = n, k_i \leq 40
12 20000 \leq 20000 mi=n,ki50 m_i = n, k_i \leq 50
13 ki10000 k_i \geq 10000
14 8000 \leq 8000 mi=n m_i = n
15 25000 \leq 25000 没有约束
16 40000 \leq 40000
17 45000 \leq 45000
18 50000 \leq 50000
19
20