#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
vector<pair<int,int>> puntos;
int minix=2e9,miniy=2e9;
int dist[2002][2002];
bool existe[2002][2002];
ll tot;
vector<pair<int,int>> bound_nivel;
vector<ll> res_temp,res_abs;
vector<ll> psum_nivel;
ll sumar(ll x,ll y){
if(x>y){
return 0;
}
ll cant=y-x+1;
return (1+cant)*cant/2;
}
int DistanceSum(int N, int *X, int *Y){
if(N<=2000){
puntos.resize(N);
for(int i=0;i<N;i++){
puntos[i]={X[i],Y[i]};
minix=min(minix,X[i]-1);
miniy=min(miniy,Y[i]-1);
}
for(int i=0;i<N;i++){
puntos[i].first-=minix;
puntos[i].second-=miniy;
existe[puntos[i].first][puntos[i].second]=true;
}
for(int i=0;i<N;i++){
//bfs
ll suma=0;
queue<pair<int,int>> bfs;
bfs.push(puntos[i]);
while(!bfs.empty()){
pair<int,int> top=bfs.front();
bfs.pop();
suma+=dist[top.first][top.second];
if(dist[top.first-1][top.second]==0 && existe[top.first-1][top.second]){
dist[top.first-1][top.second]=dist[top.first][top.second]+1;
bfs.push({top.first-1,top.second});
}
if(dist[top.first+1][top.second]==0 && existe[top.first+1][top.second]){
dist[top.first+1][top.second]=dist[top.first][top.second]+1;
bfs.push({top.first+1,top.second});
}
if(dist[top.first][top.second-1]==0 && existe[top.first][top.second-1]){
dist[top.first][top.second-1]=dist[top.first][top.second]+1;
bfs.push({top.first,top.second-1});
}
if(dist[top.first][top.second+1]==0 && existe[top.first][top.second+1]){
dist[top.first][top.second+1]=dist[top.first][top.second]+1;
bfs.push({top.first,top.second+1});
}
}
tot+=suma-2;
bfs.push(puntos[i]);
dist[puntos[i].first][puntos[i].second]=0;
while(!bfs.empty()){
pair<int,int> top=bfs.front();
bfs.pop();
if(dist[top.first-1][top.second]!=0){
dist[top.first-1][top.second]=0;
bfs.push({top.first-1,top.second});
}
if(dist[top.first+1][top.second]!=0){
dist[top.first+1][top.second]=0;
bfs.push({top.first+1,top.second});
}
if(dist[top.first][top.second-1]!=0){
dist[top.first][top.second-1]=0;
bfs.push({top.first,top.second-1});
}
if(dist[top.first][top.second+1]!=0){
dist[top.first][top.second+1]=0;
bfs.push({top.first,top.second+1});
}
}
}
return tot/2;
}else{
res_temp.resize(N);
res_abs.resize(N);
puntos.resize(N);
psum_nivel.resize(N);
bound_nivel.assign(N,{1e9,-1e9});
for(int i=0;i<N;i++){
puntos[i]={X[i],Y[i]};
minix=min(minix,X[i]);
miniy=min(miniy,Y[i]);
}
for(int i=0;i<N;i++){
puntos[i].first-=minix;
puntos[i].second-=miniy;
bound_nivel[puntos[i].first].first=min(bound_nivel[puntos[i].first].first,puntos[i].second);
bound_nivel[puntos[i].first].second=max(bound_nivel[puntos[i].first].second,puntos[i].second);
}
sort(ALL(puntos));
psum_nivel[0]=bound_nivel[0].second-bound_nivel[0].first+1;
for(int i=1;i<N;i++){
psum_nivel[i]=psum_nivel[i-1]+bound_nivel[i].second-bound_nivel[i].first+1;
}
res_abs[0]=sumar(bound_nivel[0].first+1,bound_nivel[0].second);
for(int i=1;i<N;i++){
if(puntos[i].first==puntos[i-1].first){
res_abs[i]=res_abs[i-1]+puntos[i].second-bound_nivel[puntos[i].first].first-(bound_nivel[puntos[i].first].second-puntos[i].second+1);
}else if(binary_search(ALL(puntos),make_pair(puntos[i].first-1,puntos[i].second))){
res_abs[i]=res_abs[lower_bound(ALL(puntos),make_pair(puntos[i].first-1,puntos[i].second))-puntos.begin()];
res_abs[i]+=psum_nivel[puntos[i].first-1];
res_abs[i]+=sumar(puntos[i].second+1,bound_nivel[puntos[i].first].second);
}else{
/*
caso:
.**.
****
***.
*/
int pos=lower_bound(ALL(puntos),make_pair(puntos[i].first-1,0))-puntos.begin();
res_abs[i]=res_abs[pos];
res_abs[i]+=(abs(puntos[i].first-puntos[pos].first)+abs(puntos[i].second-puntos[pos].second))*psum_nivel[puntos[pos].first];
res_abs[i]+=sumar(puntos[i].second+1,bound_nivel[puntos[i].first].second);
}
}
for(int i=0;i<N;i++){
res_temp[i]=res_abs[i];
res_temp[i]-=sumar(bound_nivel[puntos[i].first].first,puntos[i].second-1);
//res_temp[i]-=sumar(puntos[i].second+1,bound_nivel[puntos[i].first].second);
tot+=res_temp[i];
}
/*for(int i=0;i<N;i++){
tot+=sumar(bound_nivel[i].first,bound_nivel[i].second);
}*/
return tot;
}
}
