#include <bits/stdc++.h>
// meeeooowwwww mrrowwww :3
// go play vivid/stasis!! now!!!! https://vividstasis.gay
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = []{
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
return 0;
}();
map<int, set<int>> x_to_y;
map<int, set<int>> y_to_x;
struct State {
int sum = 0, total_count = 0;
vector<pair<pair<int, int>, int>> ranges;
void next(int n, const set<int> &v) {
total_count += v.size();
vector<pair<pair<int, int>, int>> new_ranges;
pair<pair<int, int>, int> new_range = {{-1, -1}, -1};
int j = 0;
for (int i : v) {
if (i <= new_range.f.s + 1) new_range.f.s = max(new_range.f.s, i), new_range.s++;
else {
if (new_range.f.f != -1) new_ranges.pb(new_range);
new_range = {{i, i}, 1};
}
for (; j < ranges.size() && ranges[j].f.f <= new_range.f.s + 1; j++) {
fo(k, ranges[j].f.f, ranges[j].f.s)
if (v.count(k)) {
ranges[j].f.f = k;
break;
}
of(k, ranges[j].f.f + 1, ranges[j].f.s + 1)
if (v.count(k)) {
ranges[j].f.s = k;
break;
}
if (ranges[j].f.f > new_range.f.s + 1) break;
if (new_range.f.f <= ranges[j].f.s + 1) new_range.f.f = min(new_range.f.f, ranges[j].f.f), new_range.f.s = max(new_range.f.s, ranges[j].f.s), new_range.s += ranges[j].s;
else {
new_ranges.pb(ranges[j]);
}
}
}
if (new_range.f.f != -1) new_ranges.pb(new_range);
for (; j < ranges.size(); j++) {
fo(k, ranges[j].f.f, ranges[j].f.s)
if (v.count(k)) {
ranges[j].f.f = k;
break;
}
of(k, ranges[j].f.f + 1, ranges[j].f.s + 1)
if (v.count(k)) {
ranges[j].f.s = k;
break;
}
new_ranges.pb(ranges[j]);
}
ranges = new_ranges;
long long curr_sum = (long long)total_count * (n + total_count);
for (auto [_, i] : ranges) curr_sum -= 2 * (long long)i*i;
sum = (sum + curr_sum % 1000000000) % 1000000000;
}
};
int DistanceSum(int n, int x[], int y[]) {
fo(i, 0, n) x_to_y[x[i]].insert(y[i]);
fo(i, 0, n) y_to_x[y[i]].insert(x[i]);
int res = 0;
{
int res_horiz = 0;
{
State s;
for (auto it = x_to_y.begin(); it != x_to_y.end(); it++) s.next(n, it->s);
res_horiz += s.sum;
}
{
State s;
for (auto it = x_to_y.rbegin(); it != x_to_y.rend(); it++) s.next(n, it->s);
res_horiz += s.sum;
}
res += res_horiz / 2 % 1000000000;
}
{
int res_vert = 0;
{
State s;
for (auto it = y_to_x.begin(); it != y_to_x.end(); it++) s.next(n, it->s);
res_vert += s.sum;
}
{
State s;
for (auto it = y_to_x.rbegin(); it != y_to_x.rend(); it++) s.next(n, it->s);
res_vert += s.sum;
}
res += res_vert / 2 % 1000000000;
}
return res % 1000000000;
}
