#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;
#define llong long long
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); // or mt19937_64
// template<class T = int> T rand(T range = numeric_limits<T>::max()) {
// return (T)(rng() % range);
// }
int DistanceSum(int n, int *x, int *y) {
map<pair<int, int>, int> points;
rep(i, n) points[{x[i], y[i]}] = i;
struct Dsu {
vector<int> root;
Dsu(int n_): root(n_) {
rep(i, len(root)) root[i] = i;
}
int find_set(int u) { return u == root[u] ? u : root[u] = find_set(root[u]); }
void join(int u, int v) {
if (rand() & 1) swap(u, v);
// clog << "join " << u << ' ' << v << endl;
root[find_set(u)] = find_set(v);
}
};
Dsu dsu(n);
rep(i, n) {
if (points.count({x[i] + 1, y[i]})) {
dsu.join(points[{x[i] + 1, y[i]}], i);
}
}
vector<set<int>> gr(n);
rep(i, n) {
auto f = points.find({x[i], y[i] + 1});
if (f == points.end()) continue;
int u = dsu.find_set(i);
int v = dsu.find_set(f->yy);
gr[u].insert(v);
gr[v].insert(u);
}
vector<pair<int, int>> gr_range(n, {INT_MAX, INT_MIN});
rep(i, n) {
int r = dsu.find_set(i);
gr_range[r].xx = min(gr_range[r].xx, x[i]);
gr_range[r].yy = max(gr_range[r].yy, x[i]);
}
auto intersect = [](pair<int, int> const& range1, pair<int, int> const& range2) -> pair<int, int> {
assert(range1.xx <= range2.yy);
assert(range2.xx <= range1.yy);
return {max(range1.xx, range2.xx), min(range1.yy, range2.yy)};
};
vector<vector<llong>> dp(n);
vector<int> tree_size(n);
llong minus_ans = 0;
function<void(int, int)> dfs = [&](int u, int p) {
int cnt = gr_range[u].yy - gr_range[u].xx + 1;
tree_size[u] = cnt;
dp[u].resize(cnt);
rep(i, cnt) {
dp[u][i] = 1ll * i * (i + 1) / 2 + 1ll * (cnt - 1 - i) * (cnt - i) / 2ll;
minus_ans += 1ll * i * (i + 1) / 2;
}
vector<llong> diff1(cnt), diff1_r(cnt);
vector<llong> diff2(cnt), diff2_r(cnt);
for (auto v: gr[u]) {
if (v == p) continue;
dfs(v, u);
tree_size[u] += tree_size[v];
auto inter = intersect(gr_range[u], gr_range[v]);
// clog << "dfs inter " << u << ' ' << p << ":" << inter.xx << ' ' << inter.yy << endl;
for (int i = inter.xx; i <= inter.yy; ++i) {
int ux = i - gr_range[u].xx, vx = i - gr_range[v].xx;
dp[u][ux] += dp[v][vx] + tree_size[v];
}
int t;
t = inter.xx - gr_range[u].xx - 1;
if (t >= 0) {
diff1_r[t] += dp[v][inter.xx - gr_range[v].xx] + tree_size[v];
diff2_r[t] += tree_size[v];
}
t = inter.yy - gr_range[u].xx + 1;
if (t < cnt) {
diff1[t] += dp[v][inter.yy - gr_range[v].xx] + tree_size[v];
diff2[t] += tree_size[v];
}
}
// clog << "dfs " << u << ' ' << p << endl;
// rep(i, cnt) clog << diff1[i] << ' '; clog << endl;
// rep(i, cnt) clog << diff2[i] << ' '; clog << endl;
// rep(i, cnt) clog << diff1_r[i] << ' '; clog << endl;
// rep(i, cnt) clog << diff2_r[i] << ' '; clog << endl;
rep(i, cnt - 1) {
diff1[i + 1] += diff1[i];
diff2[i + 1] += diff2[i];
}
for (int i = cnt - 1; i > 0; --i) {
diff1_r[i - 1] += diff1_r[i];
diff2_r[i - 1] += diff2_r[i];
}
rep(i, cnt - 1) diff2[i + 1] += diff2[i];
for (int i = cnt - 1; i > 0; --i) diff2_r[i - 1] += diff2_r[i];
rep(i, cnt) dp[u][i] += diff1[i] + diff2[i] + diff1_r[i] + diff2_r[i];
// rep(i, cnt) clog << dp[u][i] << ' ';
// clog << endl;
};
dfs(dsu.find_set(0), -1);
llong ans = 0;
for (auto& i: dp) for (auto f: i) ans += f;
ans -= minus_ans;
return (int)(ans % (1000 * 1000 * 1000));
}
