Miku

一道逆向思维的题目。

我们假设最后的最小的数是个1，放在第一个位置上，然后我们往数列开头按照规则插入0，其中应该插在这个1后面的，我们视为无效插入，插在这个1前面的，我们视为有效插入。

显然随着这个1的后退，每一次有效插入的0越来越多。那么，什么时候的插入是有效的呢，就是当1的位置加上当前的有效插入的0的数量之后已经达到了某个$a_i$的值，因为这一次删除不可能把那个1删掉，所以

这一次只有多插一个0才能保证正确。

然后模拟这个插0的过程就行了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<ctime>
#include<bitset>
using namespace std;
int t;
long long n,k;
long long a[200005];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        for(int i=1;i<=n;++i){
            scanf("%lld",&a[i]);
        }
        if(a[1]!=1) {
            printf("1\n");
            continue;
        }
        a[n+1]=1e18;
        long long pos=1;
        long long x=0;
        while(k--){
            while(x<=n&&a[x+1]<=x+pos){
                x++;
            }
            pos+=x;
        }
        cout<<pos<<endl;
    }
    return 0;
}