#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll res;
void dfs(int cur, vector<vector<int>>& g, vector<int>& st, vector<int>& s){
st[cur] = s[cur];
for (int next : g[cur]){
if (st[next] != -1) continue;
dfs(next, g, st, s);
st[cur] += st[next];
res += (ll)(n-st[next])*(ll)st[next];
}
}
ll solve(map<int,vector<int>>& m){
int cur = -1;
vector<int> s;
vector<vector<int>> g;
map<pair<int,int>,int> cc;
for (auto [x, v] : m){
sort(v.begin(), v.end());
for (int i=0; i<v.size(); i++){
if (i == 0 || v[i] != v[i-1]+1){
cur++;
s.push_back(0);
g.push_back({});
}
cc[{x, v[i]}] = cur;
s.back()++;
if (x != m.begin()->first){
if (cc.find({x-1, v[i]}) != cc.end() && (g[cur].empty() || cc[{x-1, v[i]}] != g[cur].back())){
g[cur].push_back(cc[{x-1, v[i]}]);
g[cc[{x-1, v[i]}]].push_back(cur);
}
}
}
}
vector<int> st(cur+1, -1);
res = 0;
dfs(0, g, st, s);
return res;
}
int DistanceSum(int N, int *X, int *Y){
n = N;
map<int,vector<int>> rows, cols;
for (int i=0; i<N; i++){
rows[X[i]].push_back(Y[i]);
cols[Y[i]].push_back(X[i]);
}
return (solve(rows)+solve(cols)) % 1000000000;
}
