#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[]) {
int d0[N];
vector<int> idx;
for(int i = 1; i < N; i++) {
d0[i] = getDistance(0, i);
idx.push_back(i);
}
sort(idx.begin(), idx.end(), [&](int a, int b) {return d0[a] < d0[b];});
int cl = 0, cr = *idx.begin();
location[cl] = first;
stype[cl] = 1;
location[cr] = first+d0[cr];
stype[cr] = 2;
idx.erase(idx.begin());
set<int> s1, s2;
s1.insert(location[cl]); s2.insert(location[cr]);
for(int i : idx) {
int dl = getDistance(i, cl);
int dr = getDistance(i, cr);
if(s2.count((dl-dr+location[cl]+location[cr])/2)) {
location[i] = location[cr] - dr;
stype[i] = 1;
s1.insert(location[i]);
if(location[i] < location[cl]) cl = i;
} else {
location[i] = location[cl] + dl;
stype[i] = 2;
s2.insert(location[i]);
if(location[i] > location[cr]) cr = i;
}
}
}
