(Analysis by Dhruv Rohatgi )

We are essentially asked to compute the number of pairs of lattice points $(x_1, y_1)$ and $(x_2, y_2)$, with $x_1 < x_2$ and $y_1 < y_2$, in an $N \times N$ square, where in each column there is some interval of acceptable points. Furthermore, as the $x$-coordinate of the column increases, both endpoints of the corresponding column either decrease or stay the same.

We propose a linear scan through the possibilities for $x_2$. For each $x_2$, there is some acceptable interval $[l, r]$ for the value of $y_2$. Instead of counting the number of acceptable triples $(x_1, y_1, y_2)$, we will count the number of unacceptable triples with $x_1 < x_2$ and $y_1 < y_2$ and $l \leq y_2 \leq r$, and subtract this count from the total number of such triples.

Note that if $y_2 < l$, then $y_1 < l$, so by monotonicity of interval endpoints, $(x_1,y_1)$ is itself an unacceptable point. Therefore we can drop the condition $y_2 \geq l$ entirely.

We must compute two quantities:

1) the sum over all $(x_1, y_1)$, with $x_1 < x_2$, of the number of $y_2$ with $y_1 < y_2 \leq r$.

2) the sum over all unacceptable $(x_1, y_1)$, with $x_1 < x_2$, of the number of $y_2$ with $y_1 < y_2 \leq r$.

The first quantity can be evaluated with a simple formula. To evaluate the second quantity, we divide it into two quantities: the sum where $y_1 < r$, and the sum where $y_1 \geq r$.

If $y_1 < r$, then $(x_1, y_1)$ is an unacceptable point for all $x_1 < x_2$, so this sum again has a simple closed-form formula. We turn our attention to the case $y_1 \geq r$. For each $y$, there is some bound $\text{left}(y)$ so that $(x,y)$ is unacceptable if and only if $x \leq \text{left}(y)$. For $y_1 \geq r$, this bound is no larger than $x_2$, so the set of unacceptable $(x_1,y_1)$ with $x_1 < x_2$ is in fact independent of $x_2$. So we can precompute prefix sums of $\text{left}(y)$ and prefix sums of $y \cdot \text{left}(y)$, and during our scan, for each $x_2$, we can evaluate the case-$(y_1 \geq r)$ sum in terms of these prefix sums.

Here is an implementation of the above solution.

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MAXN 100000
#define MOD 1000000007
int N;
int x[MAXN], y[MAXN];
int A[MAXN];
int top[MAXN];
int lft[MAXN];
long long sumLeft[MAXN];
long long stairSumLeft[MAXN];
int main()
	cin >> N;
	for(int i=0;i<N;i++)
		cin >> x[i] >> y[i];
		A[x[i]] = y[i];
	int low = N;
	for(int i=0;i<N;i++)
		while(A[i] < low)
			lft[--low] = i;
	while(low > 0)
		lft[--low] = N;
	sumLeft[N-1] = lft[N-1];
	for(int j=N-2;j>=0;j--)
		sumLeft[j] = (sumLeft[j+1] + lft[j])%MOD;
	stairSumLeft[N-1] = lft[N-1];
	for(int j=N-2;j>=0;j--)
		stairSumLeft[j] = (stairSumLeft[j+1] + ((long long)lft[j])*(N-j))%MOD;
	top[N-1] = A[N-1];
	for(int i=N-2;i>=0;i--)
		top[i] = max(top[i+1],A[i]);
	long long ans = 0;
	int j = N-1;
	for(int i=1;i<N;i++)
		while(j > 0 && lft[j-1] <= i)
		long long bad = stairSumLeft[j] - stairSumLeft[top[i]] - (N-top[i])*(sumLeft[j] - sumLeft[top[i]]);
		bad = ((bad%MOD)+MOD)%MOD;
		long long bad2 = (top[i]*((long long)j) - (j*((long long)(j-1)))/2)%MOD;
		bad2 = (bad2*i)%MOD;
		bad = (bad + bad2)%MOD;

		long long tot = ((top[i]*((long long)(top[i]+1)))/2)%MOD;
		tot = (tot*i)%MOD;
		ans = ans + tot - bad;
		ans = ((ans%MOD)+MOD)%MOD;
	cout << ans << '\n';