#include<bits/stdc++.h>
#include "rail.h"
#define F first
#define S second
#define sz(s) (int(s.size()))
#define PB push_back
#define bit(n, k) (((n)>>(k))&1)
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
int A[maxn], B[maxn];
map<pii, int> mp;
int ask(int a, int b){
if(a == b)
return 0;
if(mp.count({a, b}))
return mp[{a, b}];
return mp[{a, b}] = mp[{b, a}] = getDistance(a, b);
}
void findLocation(int n, int p, int location[], int stype[]){
stype[0] = 1;
location[0] = p;
if(n == 1)
return;
int mnid = 1;
for(int i = 1; i < n; i++){
A[i] = ask(0, i);
if(A[mnid] > A[i])
mnid = i;
}
int p2 = p + A[mnid];
stype[mnid] = 2;
location[mnid] = p2;
int Lid = -1, Rid = mnid;
for(int i = 0; i < n; i++){
if(i != mnid){
B[i] = ask(mnid, i);
if(Lid == -1 || B[i] < B[Lid])
Lid = i;
}
}
stype[Lid] = 1;
location[Lid] = p2 - B[Lid];
for(int i = 0; i < n; i++){
if(i != Lid)
A[i] = ask(Lid, i);
}
vector<pii> L, R;
for(int i = 0; i < n; i++){
if(i != Lid && i != Rid && i != 0){
if(A[i] < B[i]){
R.PB({A[i] - (p2 - p), i});
}
else{
L.PB({B[i] - (p2 - p), i});
}
}
}
{
vector<pii> dis;
sort(L.begin(), L.end());
for(pii p : L){
vector<int> candid;
for(int i = 0; i < sz(dis); i++){
if(dis[i].F >= p.F)
continue;
int bk = dis[i].F - (p.F - dis[i].F);
if(i == 0 && bk <= 0)
continue;
if(i != 0 && dis[i-1].F >= bk)
continue;
candid.PB(bk);
}
if(sz(candid)){
int num = ask(dis.back().S, p.S);
int bk = dis.back().F - num;
bool any = 0;
for(int x : candid)
any|= bk == x;
candid.clear();
if(any)
candid.PB(bk);
}
if(sz(candid)){
int bk = candid.back();
location[p.S] = location[Lid] - bk;
stype[p.S] = 2;
}
else{
dis.PB(p);
location[p.S] = location[Lid] - p.F;
stype[p.S] = 1;
}
}
}
{
vector<pii> dis;
sort(R.begin(), R.end());
for(pii p : R){
vector<int> candid;
for(int i = 0; i < sz(dis); i++){
if(dis[i].F >= p.F)
continue;
int bk = dis[i].F - (p.F - dis[i].F);
if(i == 0 && bk <= 0)
continue;
if(i != 0 && dis[i-1].F >= bk)
continue;
candid.PB(bk);
}
if(sz(candid)){
int num = ask(dis.back().S, p.S);
int bk = dis.back().F - num;
bool any = 0;
for(int x : candid)
any|= bk == x;
candid.clear();
if(any)
candid.PB(bk);
}
if(sz(candid)){
int bk = candid.back();
location[p.S] = location[Rid] + bk;
stype[p.S] = 1;
}
else{
dis.PB(p);
location[p.S] = location[Rid] + p.F;
stype[p.S] = 2;
}
}
}
}
