1.把原始奶牛队列可以分成，左边：可获得礼物奶牛，右边：不可获得奶牛。例，以“|”为分隔符有 ，1 2 3 4 | 5 6 7 8 9 ，即左边1 2 3 4，右边5 6 7 8 9.为什么可以分成两边。

为什么可以分成两边？
以上述例右边证明，如果 6 可获得礼物则 5 必然可以获得礼物，同理如果 2 不可获得礼物，则必然 3和4 不可获得礼物。

2.如果存在有奶牛没有礼物，则存在插队的死循环，以上例说明，1 2 3 4中存在插队死循环，而形成插队死循环的有奶牛1—4头牛。

插队死循环怎么形成的？
以上例说明。以下 i j k 为上述的1 2 3 4 的单射，即1，2，3，4任意一个数只能由 i j k其中一个表示。
如果只有1头牛形成插队死循环。那么他一定插在队伍的第一个,即C[i]=N-1。这头牛为4

如果有2头牛形成插队死循环。那么这2头牛会在队伍的第 1 位和第 2 位相互替换地插队，C[ i ]=N-2,C[ j ]=N-2. 必有一头牛为 4/ /这是个特例，当然事不过三，下面会显示特性

如果有3头牛形成插队死循环。那么这3头牛会在队伍的第 1 位，第 2 位，第 3 位相互替换地插队必有一头牛为 4 ，就可能有以下情况。
1) C[ i ]=N-2,C[ j ]=N-2，C[ k ]=N-1;
2) C[ i ]=N-2,C[ j ]=N-3，C[ k ]=N-2;
3) C[ i ]=N-2,C[ j ]=N-1，C[ k ]=N-1;
3) C[ i ]=N-3,C[ j ]=N-3，C[ k ]=N-3;//形成3头牛循环最基本条件，其中每头牛都插队到第三个。
........
规律：如果前有n头牛形成插队死循环，则其中每头牛满足N-n <= C[ i ] <= N-1.
而我们需要用二分查找 找到 5 这头牛。
代码是根据9ms 的大佬代码修改 djjdhwhhdjfkckcjj    
#include<iostream>
#include <algorithm>
#include<cstring>
using namespace std;

int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

int N;
int c[500010],pan[500010];

bool check(int mid){
    memset(pan,0,sizeof(pan));//初始化错误点，牢记 
	for(int i=1;i<mid;i++){pan[c[i]]++;}//mid前可以到达的位置。 
	for(int i=1;i<mid;i++){
        pan[i]+=pan[i-1];
	 if(pan[i]>=i){//形成死循环 
		return false;
	  }
	}
	return true;
}

int main(){
	N=read();
	c[0]=0,pan[0]=0;
	for(int i=1;i<=N;i++){
	c[i]=N-read();//当奶牛拿到礼物后，所在的队伍位置。 
	}
	int l=1,r=N,mid;
	while(l<r){
		mid=(l+r+1)>>1;
		if(check(mid)){ 
		l=mid;
		}
		else{
        r=mid-1;
		}
	}
	cout<<N-l;
}