记 $minv_i$ 为 $i$ 行及以前列编号最小的喷头的列编号，$maxv_i$ 为 $i$ 行及以后列编号最大的喷头的列编号。

考虑一个上面在 $x$ 行，下面在 $y$ 行的矩形。不难发现他的列 $l,r$ 一定满足 $minv_x\leq l\leq r<maxv_y$。

考虑用一线段树维护列右边在 $r$ 时，前面所有行不符合要求的 $l$ 总共有多少个，用另一个线段树维护列右边在 $r$，存在 $l$ 符合要求的列数。

容易发现答案就是第二个线段树 $maxv_y-1$ 位置的前缀和乘上 $maxv_y$ 再减去第一个线段树 $maxv_y-1$ 位置的前缀和。修改是容易的，每次添加一行相当于给 $minv_x\sim n$ 位置的第二个线段树加上 $1$，第一个线段树每个位置加上这个位置的编号。

总复杂度 $O(n\log n)$。

#include <bits/stdc++.h>
#define mid ((l+r)>>1) 
#define int long long
using namespace std;
const int mod=1e9+7;
int col[100005],minv[100005],maxv[100005],qz[100005];
struct sgt{
	int siz[400005],f[400005],lzt[400005];
	void pushdown(int i){
		(f[i*2]+=lzt[i]*siz[i*2])%=mod;
		(f[i*2+1]+=lzt[i]*siz[i*2+1])%=mod;
		(lzt[i*2]+=lzt[i])%=mod;
		(lzt[i*2+1]+=lzt[i])%=mod;
		lzt[i]=0;
	}
	void pushup(int i){
		f[i]=(f[i*2]+f[i*2+1])%mod;
		siz[i]=(siz[i*2]+siz[i*2+1])%mod;
	}
	void build(int i,int l,int r){
		if(l==r){
			siz[i]=qz[l];
			return ;
		}
		build(i*2,l,mid),build(i*2+1,mid+1,r);
		pushup(i);
	}
	void change(int i,int l,int r,int ql,int qr,int cg){
		if(ql<=l&&r<=qr){
			(lzt[i]+=cg)%=mod;
			(f[i]+=siz[i]*cg)%=mod;
			return ;
		}
		pushdown(i);
		if(ql<=mid) change(i*2,l,mid,ql,qr,cg);
		if(qr>mid) change(i*2+1,mid+1,r,ql,qr,cg);
		pushup(i);
	}
	int qry(int i,int l,int r,int ql,int qr){
		if(ql>qr) return 0;
		if(ql<=l&&r<=qr) return f[i];
		if(ql>r||qr<l) return 0;
		pushdown(i);
		return (qry(i*2,l,mid,ql,qr)+qry(i*2+1,mid+1,r,ql,qr))%mod;
	}
}tree1,tree2;
signed main(){
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		int u,v; cin>>u>>v;
		col[u+1]=v+1;
	}
	for(int i=1;i<=n;i++) minv[i]=maxv[i]=col[i];
	for(int i=2;i<=n;i++) minv[i]=min(minv[i],minv[i-1]);
	for(int i=n-1;i>=1;i--) maxv[i]=max(maxv[i],maxv[i+1]);
	for(int i=1;i<=n;i++) qz[i]=i; tree1.build(1,1,n);
	for(int i=1;i<=n;i++) qz[i]=1; tree2.build(1,1,n);
	int ans=0;
	for(int i=1;i<=n;i++){
		(ans+=tree2.qry(1,1,n,1,maxv[i]-1)*(maxv[i])%mod+mod-tree1.qry(1,1,n,1,maxv[i]-1))%=mod;
		tree1.change(1,1,n,minv[i],n,1);
		tree2.change(1,1,n,minv[i],n,1);
	}
	cout<<ans;
	return 0;
}