#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=3e5+10,mod=1e9+7; int n,m; int minn[maxn],mx[maxn]; int stmin[maxn][30],stmax[maxn][30],lg[maxn]; void init() { for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1; for(int i=1;i<=n;i++) stmin[i][0]=minn[i],stmax[i][0]=mx[i]; for(int i=1;i<=20;i++) { for(int j=1;j<=n;j++) { int nxt=min(j+(1<<(i-1)),n); stmin[j][i]=min(stmin[j][i-1],stmin[nxt][i-1]); stmax[j][i]=max(stmax[j][i-1],stmax[nxt][i-1]); } } } int querymin(int l,int r) { return min(stmin[l][lg[r-l+1]],stmin[r-(1<<lg[r-l+1])+1][lg[r-l+1]]); } int querymax(int l,int r) { return max(stmax[l][lg[r-l+1]],stmax[r-(1<<lg[r-l+1])+1][lg[r-l+1]]); } int ans; void sol(int l,int r) { if(l>r) return ; if(l==r) { if(mx[l]==l&&minn[l]==l) ans++; return ; } int mid=(l+r)>>1; sol(l,mid),sol(mid+1,r); vector<int> vec1,vec2; vec1.push_back(0),vec2.push_back(0); int cnt1=0,cnt2=0; for(int i=l;i<=mid;i++) if(querymin(i,mid)>=i) vec1.push_back(i),cnt1++; for(int i=mid+1;i<=r;i++) if(querymax(mid+1,i)<=i) vec2.push_back(i),cnt2++; int rlim=mid+1; for(int i=cnt1;i>=1;i--) { int lpos=vec1[i]; while(rlim<=r&&querymin(mid+1,rlim)>=lpos) rlim++; int minn=querymax(lpos,mid); int tmp=lower_bound(vec2.begin(),vec2.end(),rlim)-lower_bound(vec2.begin(),vec2.end(),minn); ans+=max(tmp,0ll); } } signed main() { ios::sync_with_stdio(false); cin>>n>>m; for(int i=1;i<=n;i++) minn[i]=mx[i]=i; int u,v; for(int i=1;i<=m;i++) { cin>>u>>v; minn[u]=min(minn[u],v); mx[u]=max(mx[u],v); } init(); sol(1,n); cout<<ans<<endl; return 0; }