#include "rail.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=1e5+10;
struct Stantia {
int d1, d2, d3;
int ind;
};
Stantia st[MAXN];
bool used[MAXN];
bool cmp(Stantia a, Stantia b) {
return a.d1<b.d1;
}
void findLocation (int n, int first, int location[], int stype[]) {
location[0]=first; stype[0]=1;
used[0]=true;
int minind=-1;
for (int i=1;i<n;i++) {
st[i].d1=getDistance(0,i);
if (minind==-1 || st[minind].d1>st[i].d1) minind=i;
}
int maxind=0, maxd=0, d;
st[0].d1=0;
for (int i=1;i<n;i++) {
if (i==minind) continue;
d=getDistance(i,0);
if (d+2*st[minind].d1==st[i].d1 && st[i].d1>st[maxind].d1) {
maxind=i;
maxd=d;
}
}
used[maxind]=true;
location[maxind]=first-maxd;
stype[maxind]=1;
int br=0;
for (int i=1;i<n;i++) {
if (i==maxind) continue;
st[br].d1=getDistance(maxind,i);
st[br].ind=i;
br++;
}
sort(st,st+br,cmp);
for (int i=0;i<br;i++) {
if (used[st[i].ind]) continue;
used[st[i].ind]=true;
location[st[i].ind]=location[maxind]+st[i].d1;
stype[st[i].ind]=2;
for (int j=i+1;j<br;j++) {
d=getDistance(st[i].ind,st[j].ind);
if (st[i].d1+d==st[j].d1) {
used[st[j].ind]=true;
location[st[j].ind]=location[st[i].ind]-d;
stype[st[j].ind]=1;
}
}
}
}
