#include <bits/stdc++.h>
/// 500 485 462 A4
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
const int MAXN=2e5+100;
map <pii,int> mp;
map <pii,int> vis;
vector <int> g[MAXN];
ll sz[MAXN];
ll dis[MAXN];
void dfs(ll v){
sz[v]=1;
for (auto u : g[v]){
dfs(u);
sz[v]+=sz[u];
}
}
void bfs(ll X,ll Y){
memset(dis,63,sizeof dis);
dis[mp[{X,Y}]]=0;
queue <pii> q;
q.push({X,Y});
dis[0]=0;
while(q.size()){
ll x=q.front().F,y=q.front().S;
q.pop();
if (dis[mp[{x-1,y}]]>dis[mp[{x,y}]]+1){
g[mp[{x,y}]].pb(mp[{x-1,y}]);
dis[mp[{x-1,y}]]=dis[mp[{x,y}]]+1;
q.push({x-1,y});
}
if (dis[mp[{x+1,y}]]>dis[mp[{x,y}]]+1){
g[mp[{x,y}]].pb(mp[{x+1,y}]);
dis[mp[{x+1,y}]]=dis[mp[{x,y}]]+1;
q.push({x+1,y});
}
if (dis[mp[{x,y-1}]]>dis[mp[{x,y}]]+1){
g[mp[{x,y}]].pb(mp[{x,y-1}]);
dis[mp[{x,y-1}]]=dis[mp[{x,y}]]+1;
q.push({x,y-1});
}
if (dis[mp[{x,y+1}]]>dis[mp[{x,y}]]+1){
g[mp[{x,y}]].pb(mp[{x,y+1}]);
dis[mp[{x,y+1}]]=dis[mp[{x,y}]]+1;
q.push({x,y+1});
}
}
dfs(mp[{X,Y}]);
}
ll hal(int N,int *X,int *Y){
ll ans=0;
for (int i=0;i<MAXN;i++) g[i].clear();
mp.clear();
vector <pii> a;
for (int i=0;i<N;i++){
a.pb({X[i],Y[i]});
}
sort(a.begin(),a.end());
for (int i=0;i<a.size();i++){
mp[a[i]]=i+1;
}
bfs(a.back().F,a.back().S);
dis[0]=1e9;
for (int i=0;i<a.size();i++){
ll j=i;
while(j<a.size() && a[j].F==a[i].F && a[j].S-a[i].S==j-i) j++;
// for (int k=i;k<j;k++){
// cout << a[k].F << " " << a[k].S << " " ;
// }
// cout << endl;
vector <ll> b;
vector <ll> w;
ll last=-1;
ll p1=0;
ll ss=0,zz=0;
for (int k=i;k<j;k++){
ll z=k;
if (dis[mp[{a[k].F-1,a[k].S}]]<dis[mp[a[k]]]) p1=1;
if (mp[{a[k].F-1,a[k].S}]==0 || dis[mp[{a[k].F-1,a[k].S}]]<dis[mp[a[k]]]) continue;
ll mx=0;
while(z<j && !(mp[{a[z].F-1,a[z].S}]==0 || dis[mp[{a[z].F-1,a[z].S}]]<dis[mp[a[z]]])){
mx=max(mx,sz[mp[{a[z].F-1,a[z].S}]]);
z++;
}
b.pb(mx);
ss+=mx;
k=z-1;
}
for (int k=i;k<j;k++){
ll z=k;
if (dis[mp[{a[k].F+1,a[k].S}]]<dis[mp[a[k]]]) p1=2;
if (mp[{a[k].F+1,a[k].S}]==0 || dis[mp[{a[k].F+1,a[k].S}]]<dis[mp[a[k]]]) continue;
ll mx=0;
while(z<j && !(mp[{a[z].F+1,a[z].S}]==0 || dis[mp[{a[z].F+1,a[z].S}]]<dis[mp[a[z]]])){
mx=max(mx,sz[mp[{a[z].F+1,a[z].S}]]);
z++;
}
w.pb(mx);
zz+=mx;
k=z-1;
}
// cout << p1 << " p1" << endl;
ll h=N-ss-zz;
if (p1==1){
b.pb(h-(j-i));
ss+=h-(j-i);
w.clear();
zz+=j-i;
w.pb(zz);
}
else{
w.clear();
zz+=h;
w.pb(zz);
}
ans+=ss*zz+ss*ss+zz*zz;
for (auto u : b) ans-=u*u;
for (auto u : w) ans-=u*u;
i=j-1;
}
return ans;
}
int DistanceSum(int N, int *X, int *Y) {
ll ans=hal(N,X,Y);
ans+=hal(N,Y,X);
return ans%(ll)(1e9);
}
/*
int main() {
int tmp;
char *inbuf, *outbuf;
inbuf = (char*) malloc(inbuf_len * sizeof(char));
outbuf = (char*) malloc(outbuf_len * sizeof(char));
tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
assert(tmp == 0);
tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
assert(tmp == 0);
int N, i;
tmp = scanf("%d", &N);
assert(tmp == 1);
int *sq_x, *sq_y;
sq_x = (int*) malloc(N * sizeof(int));
sq_y = (int*) malloc(N * sizeof(int));
for (i = 0; i < N; i++) {
tmp = scanf("%d %d", &sq_x[i], &sq_y[i]);
assert(tmp == 2);
}
int ds = DistanceSum(N, sq_x, sq_y);
printf("%d\n", ds);
return 0;
}
20
3 5
4 6
2 5
3 4
6 5
1 6
2 7
3 1
2 6
1 5
5 5
5 4
4 7
4 2
3 2
3 3
4 4
4 3
4 5
5 2
*/
