4287: 「CTSC2017」最长上升子序列
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
猪小侠最近学习了最长上升子序列的相关知识。对于一个整数序列 $ 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提示
数据范围： | 测试点 | $ n $ | 约束 | |-|-|-| | 1 | $ \leq 50000 $ | $ k_i = 1 $ | | 2 | $ \leq 300 $ | $ k_i \leq 2 $ | | 3 | $ \leq 3000 $ | $ k_i \leq 2 $ | | 4 | $ \leq 50000 $ | $ b_i \leq 5 $ | | 5 | $ \leq 50000 $ | $ b_i \leq 8 $ | | 6 | $ \leq 100 $ | $ m_i = n $ | | 7 | $ \leq 100 $ | $ m_i = n $ | | 8 | $ \leq 800 $ | $ m_i = n, k_i \leq 10 $ | | 9 | $ \leq 1500 $ | $ m_i = n, k_i \leq 10 $ | | 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 | $ \leq 20000 $ | $ k_i \geq 10000 $ | | 14 | $ \leq 8000 $ | $ m_i = n $ | | 15 | $ \leq 25000 $ | 没有约束 | | 16 | $ \leq 40000 $ | 没有约束 | | 17 | $ \leq 45000 $ | 没有约束 | | 18 | $ \leq 50000 $ | 没有约束 | | 19 | $ \leq 50000 $ | 没有约束 | | 20 | $ \leq 50000 $ |