/*
w1 | i
----------
?(p) | w2
*/
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=1e5;
const int MOD=1e9;
pair<int,int> t[NN+10];
map<pair<int,int>,int> id;
long long ans[NN+10];
long long siz[NN+10];
pair<long long,long long> dans[NN+10];
void set_siz(int l,int r,long long c)
{
for(int i=l;i<=r;i++)
siz[i]=c;
return;
}
void add_ans(int l,int r,long long a,long long d) // a - value in r+1
{
dans[r].fi+=a+d;
dans[r].se+=d;
dans[l-1].fi-=(a+d*(r-l+2))%MOD;
dans[l-1].se-=d;
return;
}
void recalc(int l,int r)
{
long long c=0,d=0;
for(int i=r;i>=l;i--,c+=d)
{
c+=dans[i].fi;
d+=dans[i].se;
c%=MOD;
d%=MOD;
ans[i]=(ans[i]+c)%MOD;
}
return;
}
int DistanceSum(int N,int *X,int *Y)
{
int n=N;
for(int i=0;i<n;i++)
t[i+1]={X[i],Y[i]};
sort(t+1,t+n+1);
int bg=1;
long long w=0;
for(int i=1;i<=n;i++)
{
id[t[i]]=i;
if(i>1 && (t[i].fi!=t[i-1].fi || t[i].se!=t[i-1].se+1))
{
recalc(bg,i-1);
set_siz(bg,i-1,siz[i-1]);
bg=i;
}
int w1=id[make_pair(t[i].fi-1,t[i].se)];
int w2=i-1;
int p=w1-1;
if(w1==0 && bg==i) // no w1 nor w2
{
ans[i]=0;
siz[i]=1;
}
else if(w1==0) // no w1
{
ans[i]=(ans[w2]+siz[w2])%MOD;
siz[i]=siz[w2]+1;
add_ans(bg,i-1,0,1);
}
else if(bg==i) // no w2
{
ans[i]=(ans[w1]+siz[w1])%MOD;
siz[i]=siz[w1]+1;
}
else if(w1==1 || t[w1-1].fi!=t[w1].fi || t[w1-1].se!=t[w1].se-1) // no ?
{
ans[i]=(ans[w1]+ans[w2]+siz[w1]+siz[w2])%MOD;
siz[i]=siz[w1]+siz[w2]+1;
w+=(ans[w1]+siz[w1])*siz[w2]+(ans[w2]+siz[w2])*siz[w1];
w%=MOD;
add_ans(bg,i-1,ans[w1]+siz[w1],siz[w1]+1);
}
else // with ?
{
ans[i]=(ans[w1]+ans[w2]-ans[p]-siz[p]+siz[w2])%MOD;
siz[i]=siz[w2]+1;
add_ans(bg,i-1,0,1);
}
w=(w+ans[i])%MOD;
//cerr<<t[i].fi<<" "<<t[i].se<<": "<<w<<"\n";
}
//recalc(bg,n);
//for(int i=1;i<=n;i++)
// cerr<<t[i].fi<<" "<<t[i].se<<": "<<ans[i]<<" "<<siz[i]<<"\n";
return (w+MOD)%MOD;
}
