#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans[5050][5050], O;
int myquery(int i, int j){
--i, --j;
if (i==j) return 0;
if (i>j) swap(i, j);
return ans[i][j]?ans[i][j]:ans[i][j]=getDistance(i, j);
}
bool cmp(int i, int j){
return myquery(O, i) < myquery(O, j);
}
void solve(int s1, int s2, int pos1, int pos2, vector<int> C, int loc[], int typ[]){
O = s1;
sort(C.begin(), C.end(), cmp);
vector<pair<int, int>> P = {{s2, pos2}};
int R = s2, pR = pos2;
for (auto &i:C){
//printf(" %d %d %d -> ", s1, s2, i);
if (myquery(s1, i) < myquery(s1, s2)) {
//printf(" YES %d %d %d\n", s1, s2, i);
loc[i] = pos1 + myquery(s1, i), typ[i] = 2;
P.emplace_back(i, loc[i]);
continue;
}
int pos3 = pos2 - (myquery(R, i) - (myquery(s1, i)-myquery(s1, R)))/2;
for (auto &[idx, pos]:P) if (pos==pos3){
loc[i] = pR - myquery(R, i);
typ[i] = 1;
break;
}
if (typ[i]!=1){
loc[i] = pos1 + myquery(s1, i);
typ[i] = 2;
P.emplace_back(i, loc[i]);
R = i, pR = loc[i];
//printf(" %d -> %d %d\n", i, typ[i], loc[i]);
}
}
}
void findLocation(int N, int first, int location[], int stype[]){
if (N==1) {location[0] = first, stype[0] = 1; return;}
int n = N, s1 = 1, s2;
int val = 1e9;
for (int i=2;i<=n;i++) if (val > myquery(s1, i)) val = myquery(s1, i), s2 = i;
location[s1-1] = first, location[s2-1] = first + val;
stype[s1-1] = 1, stype[s2-1] = 2;
vector<int> L, R;
for (int i=1;i<=n;i++) if (i!=s1 && i!=s2){
if (myquery(s1, i) < myquery(s2, i)) R.push_back(i);
else L.push_back(i);
}
solve(s1, s2, location[s1-1], location[s2-1], R, location-1, stype-1);
solve(s2, s1, -location[s2-1], -location[s1-1], L, location-1, stype-1);
for (auto &i:L) location[i-1] = -location[i-1], stype[i-1] = ((stype[i-1]-1)^1)+1;
}
