记录编号	540293	评测结果	AAAAAAAAAA
题目名称	[Vijos1369] 难解的问题	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.064 s
提交时间	2019-08-19 21:37:48	内存使用	18.23 MiB

#include<bits/stdc++.h>
#define I inline
using namespace std;
const int N=3e5+7;
int a[N],low[N],b[N],c[N];
int n,k,m,cnt,ans;
I int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-')f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	freopen("muzuka.in","r",stdin);
	freopen("muzuka.out","w",stdout);
	n=read(),k=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<k;i++) if (a[i]<a[k]) b[++m]=a[i];
	for (int i=k+1;i<=n;i++) if (a[i]>a[k]) c[++cnt]=a[i];
	int tot=1;low[tot]=b[tot];
	if (!m) tot--;
	for (int i=2;i<=m;i++)
	{
		if (b[i]>low[tot]) low[++tot]=b[i];
		else 
		{
			int pos=lower_bound(low+1,low+tot+1,b[i])-low;
			low[pos]=b[i];
		}
	}
	ans=tot;
	memset(low,0,sizeof(low));tot=0;
	if (!cnt) tot--;
	low[++tot]=c[tot];
	for (int i=2;i<=cnt;i++)
	{
		if (c[i]>low[tot]) low[++tot]=c[i];
		else 
		{
			int pos=lower_bound(low+1,low+tot+1,c[i])-low;
			low[pos]=c[i];
		}
	}
	ans+=tot+1;
	printf("%d\n",ans);
	return 0;
}