请注意，这是正解

考虑设 $f_i$ 表示在第 $i$ 个人是女生时，在 $[1,i]$ 当中最多有多少个人是女生。特别的，如果 $f_i=0$ 则表示该位置不能是女生。

那么我们考虑进行 dp，很显然 dp 式子大概是：

我们来考虑 $k$ 应该满足哪些条件。

1. 不应存在一条限制覆盖区间 $[k,i]$。
2. 不应存在一条限制被区间 $(k,i)$ 包含。

对于第一个条件，显然能够算出距离你最近的满足条件的 $k$ 是多少；对于第二个条件，显然能够算出距离你最远的满足条件的 $k$ 是多少。

所以满足条件的 $k$ 一定是一个区间，随便用什么东西维护一下 $f$ 的 RMQ 即可，我采用的是线段树，$O(n\log n)$ 解决战斗。

注意到，满足条件的 $k$ 的区间在 $i$ 不断变大时，左端点单调不降，右端点单调不降，所以用单调队列维护那个最小值即可 $O(n)$ 解决战斗。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll int
#define lc (x<<1)
#define rc ((x<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
const ll N=2e5+10;
const ll M=1e5+10;
struct node{ll L,R;}dat[M];
bool cmp1(node x,node y){return x.L<y.L;} 
bool cmp2(node x,node y){return x.R>y.R;}
bool cmp3(node x,node y){return x.R<y.R;}
bool cmp4(node x,node y){return x.L>y.L;}
ll n,m,lft[N],rgt[N],top,f[N],maxx[N<<2];
inline void push_up(ll x){maxx[x]=max(maxx[lc],maxx[rc]);}
void chg(ll x,ll l,ll r,ll p,ll v){
	if(l==r){maxx[x]=v;return;}
	if(p<=mid) chg(lc,l,mid,p,v);
	else chg(rc,mid+1,r,p,v);
	push_up(x);
}
ll query(ll x,ll l,ll r,ll L,ll R){
	if(L<=l&&r<=R) return maxx[x];
	ll ret=-1;
	if(L<=mid) ret=max(ret,query(lc,l,mid,L,R));
	if(R>mid) ret=max(ret,query(rc,mid+1,r,L,R));
	return ret; 
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	if(m==0){cout<<n;return 0;}
	for(ll i=1;i<=m;i++) cin>>dat[i].L>>dat[i].R;
	for(ll i=1;i<=n;i++) lft[i]=rgt[i]=i;
	sort(dat+1,dat+1+m,cmp1);top=1;
	ll minn=-1;
	for(ll i=1;i<=n;i++){
		while(top<=m&&dat[top].L<=i){minn=max(minn,dat[top].R);top++;}
		rgt[i]=max(rgt[i],minn);
	}
	minn=n;
	sort(dat+1,dat+1+m,cmp2);top=1;
	for(ll i=n;i>=1;i--){
		while(top<=m&&dat[top].R>=i){minn=min(minn,dat[top].L);top++;}
		lft[i]=min(lft[i],minn);
	}
	sort(dat+1,dat+1+m,cmp3);top=1;
	ll now=0;minn=1;
	for(ll i=1;i<=n;i++){
		while(now<n&&rgt[now+1]<i) now++;
		if(i==1) f[i]=1;
		else{
			if(minn>min(lft[i]-1,now)) f[i]=0;
			else{
				f[i]=query(1,1,n,minn,min(lft[i]-1,now));
				if(f[i]) f[i]++;
			}
		}
		if(top==1) f[i]=max(f[i],1);
		chg(1,1,n,i,f[i]);
		while(top<=m&&dat[top].R<=i){minn=max(minn,dat[top].L);top++;}
	}
	sort(dat+1,dat+1+m,cmp4);
	ll ans=0;
	for(ll i=n;i>=1;i--){
		ans=max(ans,f[i]);
		if(dat[1].L>=i) break;
	}
	if(ans==0) cout<<"-1";
	else cout<<ans; 
	return 0;
}