In my code,I have set a limit on the number of iterations but it still Time limit exceeded.

Can anyone tell me how to find the next faster or explain that my code complexity is incorrect.

#include <bits/stdc++.h>
//#define int long long
#define pb push_back
using namespace std;
const int M=(int)(2e5),N=(int)(2e5+5);

#define ls ((cur)<<1)
#define rs ((ls)|1)
int n,a[N],mi[N<<2],sum[N],MX,ct0,ct[N];

inline void upt(int x,int v) {
	ct[x]+=v;
	while(x<=MX) sum[x]+=v,x+=(x&(-x));
}

inline int qry(int x) {
	int res=0; while(x) res+=sum[x],x-=(x&(-x)); return res;
}

void push_up(int cur) {
	mi[cur]=min(mi[ls],mi[rs]);
} 

void upt_add(int cur,int l,int r,int pos,int v) {
	if(l==r) {
		mi[cur]+=v; upt(l,v);
		return ;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) upt_add(ls,l,mid,pos,v);
	else upt_add(rs,mid+1,r,pos,v);
	push_up(cur);
}

int qry_nex(int cur,int l,int r,int cl,int cr,int v) {
	if(mi[cur]>=v) return -1;
	if(l==r) return l;
	int mid=(l+r)>>1;
	if(cl<=l&&r<=cr) {
		if(mi[cur]>=v) return -1;
		if(mi[rs]<v) return qry_nex(rs,mid+1,r,cl,cr,v);
		return qry_nex(ls,l,mid,cl,cr,v);
	}
	if(cr<=mid) return qry_nex(ls,l,mid,cl,cr,v);
	if(cl>mid) return qry_nex(rs,mid+1,r,cl,cr,v);
	if(mi[rs]<v) {
		int qwq=qry_nex(rs,mid+1,r,cl,cr,v);
		if(qwq!=-1) return qwq;
	}
	return qry_nex(ls,l,mid,cl,cr,v);
}

bool chk(int Lim,int re) {
	re*=2;
	int nw=Lim-1,tmp=qry(MX)-qry(Lim-1),need=1;
	while(nw>=1) {
		int pos=qry_nex(1,1,MX,1,nw,need);
//		cout<<nw<<" "<<pos<<" "<<need<<" "<<qry_ct(1,0,MX,pos,pos)<<'\n';
		if(pos<1) {
			tmp+=qry(nw)-nw*need;
			break ;
		}
		int qwq=0;
		if(pos<nw) {
//			qwq=qry_ct(1,0,MX,pos+1,nw)-(nw-pos)*need;
			qwq=qry(nw)-qry(pos);
			re-=qwq; tmp+=qwq-(nw-pos)*need;
		}
		need+=need-(ct[pos]);
		if(need>re) {
			return 0;
		}
		nw=pos-1;
	}
	bool fl=0;
//	cout<<qry_ct(1,0,MX,0,0)+tmp<<'\n';
	if(ct0+tmp>=need) fl=1;
	return fl;
}
 
void sol() {
	cin>>n; MX=n; ct0=0;
	for(int i=1;i<=n;i++) cin>>a[i];
	int res=1;
	for(int i=1;i<=n;i++) {
		if(a[i]&&a[i]<=MX) upt_add(1,1,MX,a[i],1);
		else ++ct0;
		if(i==1) {
			cout<<max(1,a[i])<<' ';
			continue ;
		}
		while(chk(res+1,i)) ++res;
		cout<<res<<' ';
	}
	cout<<'\n';
	memset(mi,0,sizeof(int)*(4*n+1));
	memset(sum,0,sizeof(int)*(n+1));
	memset(ct,0,sizeof(int)*(n+1));
}

signed main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int T; cin>>T; while(T--) sol();
	return 0;
}