$ color{#0066ff}{ 题目描述 }$
有 N((1≤N≤10^5))头牛按顺序排成一列，编号从 1 到 N，1 号牛在队头，N 号牛在队尾。
每次位于队头的牛 i 拿到一个礼物，然后插入到从队尾数(c_i)头牛之前的位置。。举个栗子： 初始队列 1,2,3,4,5 (c_1) = 2，(c_2) = 3，则第一次操作后的序列为 2,3,1,4,5，第二次操作后的序列为 3,2,1,4,5。重复无限次操作，求最后有几头牛拿不到礼物。
(color{#0066ff}{输入格式})
第一行一个整数n，接下来一行为(c_i)
(color{#0066ff}{输出格式})
输出一行为ans
(color{#0066ff}{输入样例})
3
1 2 0
(color{#0066ff}{输出样例})
1
(color{#0066ff}{数据范围与提示})
(1 leq N leq 10^5),
(color{#0066ff}{题解})
可以发现，如果一头牛无法拿到礼物，那么它后面的牛一定无法拿到礼物，因为相对顺序不变
于是这就具有了可二分性，我们可以二分那个最靠前的不能拿到礼物的牛是谁，就能获知答案
那么现在要考虑的就是如何判断一头牛能否拿到礼物
一头牛能拿到礼物，当且仅当它能排到队首，那么如何让它往前移动？？ 其实便是前面的牛拿完礼物排在了它的后面，这样它其实就是往前了
可以开一个桶统计一下他前面的人的到达位置的个数的后缀和（开个桶统计到达位置，求后缀和）
那么(t[i])就代表当前它前面有多少牛拿完礼物后可以到达i以及i之后的位置
那么当前它能移动的距离其实就是自己位置的桶，最后只要判它能不能到1即可
#include <cstdio>
#include <iostream>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
template<class T> bool chkmax(T &a, const T &b) { return a < b? a = b, 1 : 0; }
template<class T> bool chkmin(T &a, const T &b) { return b < a? a = b, 1 : 0; }
const int maxn = 2e5 + 100;
int n, c[maxn], t[maxn];
bool ok(int x) {
for(int i = 1; i <= n; i++) t[i] = 0;
for(int i = 1; i <= x - 1; i++) t[n - c[i]]++;
for(int i = n; i >= 1; i--) t[i] += t[i + 1];
int now = x, nowtot = 0;
for(int i = x; i >= 1; i--) {
if(i < now) break;
now = now - (t[i] - nowtot);
nowtot += t[i] - nowtot;
}
return now != 1;
}
int main() {
n = in();
for(int i = 1; i <= n; i++) c[i] = in();
int l = 1, r = n, ans = n + 1;
while(l <= r) {
int mid = (l + r) >> 1;
if(ok(mid)) r = mid - 1, ans = mid;
else l = mid + 1;
}
printf("%d
", n - ans + 1);
return 0;
}