//9:45 50pt #include<bits/stdc++.h> using namespace std; #define int long long const int MAXN=100010,Mod=1000000007; int n,m,ans,p[MAXN],q[MAXN],L[MAXN],R[MAXN]; void fz(int l,int r){ if(l>r)return; if(l==r){ if(q[l]==p[l]){ //cout<<l<<" "<<ans<<"++"<<endl; ans++; } return; } int mid=(l+r)>>1; //cout<<"LRM: "<<l<<" "<<r<<" "<<mid<<endl; int pm=p[mid],qm=q[mid]; for(int i=mid;i>=l;i--){ pm=min(pm,p[i]); L[i]=(pm>=i); } for(int i=mid;i<=r;i++){ qm=max(qm,q[i]); R[i]=(qm<=i); } R[mid-1]=0; //for(int i=l;i<=r;i++){ // cout<<((i<=mid)?L[i]:R[i])<<" "; //} //cout<<endl; int Q=q[mid]; for(int i=mid;i<=r;i++)R[i]+=R[i-1]; //for(int i=l;i<=r;i++){ // cout<<((i<=mid)?L[i]:R[i])<<" "; //} //cout<<endl; for(int i=mid,j=mid;i>=l;i--,Q=max(q[i],Q)){ while(i>=l&&!L[i]){ i--; Q=max(q[i],Q); } if(i<l)break; while(j<=r&&p[j]>=i)j++; //cout<<" "<<i<<" "<<j<<" "<<Q<<endl; ans+=j>Q?R[j-1]-R[Q-1]:0; //cout<<"ans+="<<R[j-1]-R[Q-1]<<":"<<j-1<<" "<<R[j-1]<<" "<<Q-1<<" "<<R[Q-1]<<endl; } fz(l,mid-1); fz(mid+1,r); } signed main(){ scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++)q[i]=p[i]=i; for(int i=1;i<=m;i++){ int u,v; scanf("%lld%lld",&u,&v); p[u]=(p[u])?min(p[u],v):v; q[u]=max(q[u],v); } // for(int i=1;i<=n;i++)cout<<p[i]<<" "<<q[i]<<endl; fz(1,n); printf("%lld",ans); return 0; }