记录编号	108513	评测结果	AAAAAAAAAAA
题目名称	134.[USACO Feb08] 晚餐队列安排	最终得分	100
用户昵称	JSX	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2014-07-04 20:51:19	内存使用	0.52 MiB

#include<cstdio>
#include<cstring>
using namespace std;

int nHigh[30001]={0};
int nDate[30001]={0};
int N=0;

int main()
{
	freopen("diningb.in","r",stdin);
	freopen("diningb.out","w",stdout);
	scanf("%d",&N);
	
	for(int i=1;i<=N;++i)
	{
		scanf("%d",&nHigh[i]);
	}
	
	//printf("%d\n",nHigh[11]);
	int head=0,tail=0,mid=0,nLen=0;
	
	/*for(int i=1;i<=N;++i)
	{
		head=1;
		tail=nLen;
		
		while(head<=tail)
		{
			mid=(head+tail)/2;
			if(nHigh[i]<=nDate[mid])
			{
				head=mid+1;
			}
			else
			{
				tail=mid-1;
			}
		}
		
		if(head>nLen)
		{
			nLen=head;
			printf("i=%d\n",i);
		}
		 
		nDate[head]=nHigh[i];
	}
	
	
	printf("%d\n",nDate[12]);*/
	int s1,s2;
	s1=1000000000;
	
	nLen=0;
	memset(nDate,0,sizeof(nDate));
	
	for(int i=1;i<=N;++i)
	{
		head=1;
		tail=nLen;
		
		while(head<=tail)
		{
			mid=(head+tail)/2;
			if(nHigh[i]>=nDate[mid])
			{
				head=mid+1;
			}
			else
			{
				tail=mid-1;
			}
		}
		
		if(head>nLen)
		{
			nLen=head;
		}
		 
		nDate[head]=nHigh[i];
	}
//	printf("%d\n",nLen);
	s2=N-nLen;
	
	if(s1>s2) printf("%d",s2);
	else printf("%d",s1);
	
	return 0;
}