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

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

题目描述

猪小侠最近学习了最长上升子序列的相关知识。对于一个整数序列 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, \ldots, 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 行,按顺序每行一个整数作为回答。

样例

样例输入

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) ,它的最长上升子序列长度为 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

数据范围与提示

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