UOJ Logo Sharp Sword 剑锋 OI

SSOI

#29. 含有第K项LIS

统计

【问题描述】

给定一个序列.求最长上升子序列(lis)p1。
但是,现在还有一个附加条件:求出的最长上升子序列必须含有第K项。
比如,在上面的例子中,要求求出的最长上升子序列必须含有第6项,那么最长上升子序列就是:65 155 207 389

【输入格式】

第一行是用空格隔开的两个正整数N、K,含义同上所述。
第二行N个数,即给出的序列。

【输出格式】

仅有一个数,表示含有第K项的最长上升子序列的长度

【输入样例1】

5 3
1 2 3 2 1

【输出样例1】

3

【时空限制】

1S
256MB
对于60%的数据,N<=10000;
对于100%的数据,1<=n<=300000 ,1<=k<=n,序列的每一个数为小于2^31-1 的非负整数。