记录编号	521771	评测结果	AAAAAAAAAA
题目名称	[USACO Open18 Gold] Out of Sorts	最终得分	100
用户昵称	夜未央	是否通过	通过
代码语言	C++	运行时间	0.104 s
提交时间	2018-11-07 20:53:52	内存使用	0.82 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
	int num;
	int v;
} a[100010];
int ans=1,pp;
int n,i;
bool bk[100010];
bool cmp(node a1,node a2){
	if(a1.v==a2.v){
		return a1.num<a2.num;
	} 
	return (a1.v<a2.v);
}
inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch<='0'||ch>'9')
	{
		if(ch=='-')w=-1;ch=getchar();
	}   
	while(ch>='0'&&ch<='9')
		s=s*10+ch-'0',ch=getchar();
	return s*w;
    }
inline void write(int x)
    {
         if(x<0) putchar('-'),x=-x;
         if(x>9) write(x/10);
         putchar(x%10+'0');
}
int cgy()
{
	freopen("sort_gold_18open.in","r",stdin);
	freopen("sort_gold_18open.out","w",stdout);
		ios::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<=n;i++){
    	cin>>a[i].v;
    	a[i].num=i;
    }
    sort(a+1,a+n+1,cmp);
    for(i=1;i<=n;i++)
    {
        if(i<a[i].num){
        	pp++;
        }
        if(bk[i]){
        	pp--;
        }
    	bk[a[i].num]=true;
        ans=max(ans,pp);
    }
    cout<<ans<<endl;
}
int clz=cgy();
int main(){;}
/*
5
1
8
5
3
2

2
*/