#include <bits/stdc++.h>
using namespace std;
int lim;
queue<int> camino;
struct nodo{
int familia=0;
int pa=0;
int pb=0;
long long int cantidad=0;
int lvl=0;
vector<int> conexiones;
};
nodo arbol[100001];
pair<int,int> valores[100001];
void ciclo(int pos){
while(camino.size()>0){
int aux=camino.front();
if(arbol[pos].familia>arbol[aux].familia+1) camino.pop();
else if(arbol[pos].familia>arbol[aux].familia){
if(arbol[aux].pa>arbol[pos].pb) break;
if((arbol[aux].pa>=arbol[pos].pa)||(arbol[aux].pa<arbol[pos].pa&&arbol[aux].pb>=arbol[pos].pa)){
arbol[pos].conexiones.push_back(aux);
arbol[pos].lvl++;
arbol[aux].conexiones.push_back(pos);
arbol[aux].lvl++;
}
if(arbol[aux].pb<=arbol[pos].pb) camino.pop();
else break;
}
else break;
}
}
void generar_arbol(){
int pos=0;
arbol[0].familia=valores[0].first;
arbol[0].pa=valores[0].second; arbol[0].pb=valores[0].second;
arbol[0].cantidad=1;
pair<int,int> anterior=valores[0];
swap(valores[0].first,valores[0].second);
for(int i=1;i<lim;i++){
if(anterior.first==valores[i].first&&valores[i].second-anterior.second==1){
arbol[pos].cantidad++;
arbol[pos].pb=valores[i].second;
}
else{
ciclo(pos);
camino.push(pos);
pos++;
arbol[pos].cantidad=1;
arbol[pos].familia=valores[i].first; arbol[pos].pa=valores[i].second; arbol[pos].pb=valores[i].second;
}
anterior=valores[i];
swap(valores[i].first,valores[i].second);
}
ciclo(pos);
while(camino.size()>0){
camino.pop();
}
}
void encontrar_extremos(int padre=-1, int pos=0){
if(arbol[pos].lvl==1) camino.push(pos);
for(int nod: arbol[pos].conexiones){
if(nod!=padre) encontrar_extremos(pos,nod);
}
}
long long int pasos(){
long long int sum=0;
while(camino.size()>0){
nodo reiniciar;
int aux=camino.front();
sum+=(arbol[aux].cantidad*(lim-arbol[aux].cantidad))%1000000000;
sum%=1000000000;
arbol[aux].lvl--;
for(int nod:arbol[aux].conexiones){
if(arbol[nod].lvl>=1){
arbol[nod].lvl--;
arbol[nod].cantidad+=arbol[aux].cantidad;
if(arbol[nod].lvl==1) camino.push(nod);
else if(arbol[nod].lvl==0) arbol[nod]=reiniciar;
}
}
arbol[aux]=reiniciar;
camino.pop();
}
return sum;
}
int DistanceSum(int N, int *X, int *Y) {
long long int total=0;
for(int i=0;i<N;i++){
valores[i]={X[i],Y[i]};
}
sort(valores,valores+N);
lim=N;
generar_arbol();
encontrar_extremos();
total=pasos();
sort(valores,valores+N);
generar_arbol();
encontrar_extremos();
total+=pasos();
total%=1000000000;
return total;
}
