#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll res = 0;
vector<vector<int>> g;
vector<bool> seen;
void bfs(int s){
seen.assign(n, false);
queue<pair<int,ll>> q;
q.push({s, 0});
while (!q.empty()){
int cur = q.front().first, d = q.front().second;
q.pop();
if (seen[cur]) continue;
seen[cur] = true;
if (cur > s) res += d;
for (int next : g[cur]) q.push({next, d+1});
}
}
int DistanceSum(int N, int *X, int *Y){
n = N;
g.resize(N);
for (int i=0; i<N-1; i++){
for (int j=i+1; j<N; j++){
if (abs(X[i]-X[j])+abs(Y[i]-Y[j]) == 1){
g[i].push_back(j);
g[j].push_back(i);
}
}
}
for (int i=0; i<N; i++) bfs(i);
return res % 1000000000;
}
