#include "rail.h"
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN=1e5+10;
const int MAXM=1e6+10;
struct Stantia {
int d;
int ind;
};
Stantia st[MAXN];
int dist[2][MAXN];
int um[MAXM];
bool cmp(Stantia a, Stantia b) {
return a.d<b.d;
}
void findLocation (int n, int first, int location[], int stype[]) {
location[0]=first; stype[0]=1;
memset(um,-1,sizeof(um));
for (int i=1;i<n;i++) {
st[i].d=dist[0][i]=getDistance(0,i);
st[i].ind=i;
}
sort(st+1,st+n,cmp);
location[st[1].ind]=first+st[1].d;
stype[st[1].ind]=2;
int mini=0, maxi=st[1].ind;
um[location[0]]=0; um[location[st[1].ind]]=st[1].ind;
for (int i=0;i<n;i++) {
if (i==st[1].ind) continue;
dist[1][i]=getDistance(st[1].ind,i);
}
int l1, d1;
for (int i=2;i<n;i++) {
int cur=st[i].ind;
if (dist[1][cur]+st[1].d!=st[i].d) {
d1=getDistance(maxi,cur);
l1=(dist[0][maxi]+d1-dist[0][cur])/2;
l1=location[maxi]-l1;
if (um[l1]!=-1 && stype[um[l1]]==2) {
location[cur]=location[maxi]-d1;
stype[cur]=1;
} else {
location[cur]=location[0]+dist[0][cur];
stype[cur]=2;
maxi=cur;
}
///cout << "up " << st[i].ind << ' ' << location[st[i].ind] << endl;
um[location[st[i].ind]]=st[i].ind;
}
}
for (int i=2;i<n;i++) st[i].d=dist[1][st[i].ind];
sort(st+2,st+n,cmp);
for (int i=2;i<n;i++) {
int cur=st[i].ind;
if (dist[1][cur]+st[1].d==dist[0][cur]) {
d1=getDistance(mini,cur);
l1=(dist[1][mini]+d1-dist[1][cur])/2;
l1=location[mini]+l1;
if (um[l1]!=-1 && stype[um[l1]]==1) {
location[cur]=location[mini]+d1;
stype[cur]=2;
} else {
location[cur]=location[st[1].ind]-dist[1][cur];
stype[cur]=1;
mini=cur;
}
///cout << cur << ' ' << location[cur] << endl;
um[location[st[i].ind]]=st[i].ind;
}
}
}
