记录编号	244311	评测结果	AAAAAAAAAAAAAAA
题目名称	2201.[USACO Dec15] 卡牌游戏(银组)	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.372 s
提交时间	2016-03-31 18:24:12	内存使用	1.55 MiB

/*
ID:satoshi
TASK:highcard
LANG:C++
*/
#include <fstream>
#include <algorithm>
#include <set>
#include <functional>
#define N 100010
using namespace std;
ifstream cin("highcard.in");
ofstream cout("highcard.out");
bool l[N]={0};
int n,ans=0;
int pre[N]={0},suffix[N]={0};
int S[N]={0};
set<int> A;
set<int,greater<int> >B;
void read()
{
	int i,x;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>x;
		S[i]=x;
		l[x]=1;
	}
	for(i=1;i<=2*n;i++)
	{
		if(!l[i])
		{
			A.insert(i);
			B.insert(i);
		}
	}
}
void work()
{
	int i,tot;
	set<int>::iterator it;
	set<int,greater<int> >::iterator ot;
	tot=0;
	for(i=1;i<=n;i++)
	{
		it=A.upper_bound(S[i]);
		if(it==A.end())A.erase(A.begin());//以小抵大
		else
		{
			A.erase(it);
			tot++;
		}
		pre[i]=tot;
	}
	tot=0;
	for(i=n;i>=1;i--)
	{
		ot=B.upper_bound(S[i]);
		if(ot==B.end())B.erase(B.begin());
		else
		{
			B.erase(ot);
			tot++;
		}
		suffix[i]=tot;
	}
	cout<<pre[n]<<endl;
}
int main()
{
	read();
	work();
	return 0;
}