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

/*
ID:satoshi
TASK:cardgame
LANG:C++
*/
/*
题解：贪心+维护前缀后缀和
类似于田忌赛马，只不过没有重复的卡片
我们使用两个set,第一个set对于Elsie的当前卡片，找到最小的比当前卡片大的Bessie卡片（以最小的代价得分）
如果没有卡片比当前卡片大，使用最小的卡片"以最小的代价毁掉了"大卡片，维护前i个卡片最多能"高分赢"的得分数
第二个set反其道而行之，维护后i个卡片最少能"低分赢"的得分数
则答案就是{max(pre[i]+sum[i+1])}
*/
#include <fstream>
#include <algorithm>
#include <set>
#include <functional>
#define N 100010
using namespace std;
ifstream cin("cardgame.in");
ofstream cout("cardgame.out");
bool l[N]={0};
int n,ans=0;
int pre[N]={0},suffix[N]={0};//前缀，后缀
int S[N]={0};//Elsie的数字序列
set<int> A;//Bessie升序
set<int,greater<int> >B;//Bessie降序
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;//维护低分后缀
	}
	for(i=0;i<=n;i++)ans=max(ans,pre[i]+suffix[i+1]);//注意边界，枚举改变规则的分界点
	cout<<ans<<endl;
}
int main()
{
	read();
	work();
	return 0;
}