#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[]){
bitset <1000001> bs;
int d[N],mn=1e9,l=0,r=-1;
location[0]=first;
stype[0]=1;
vector <pair <int, int>> ve;
vector <int> vl;
for (int i=1;i<N;i++){
d[i]=getDistance(0,i);
if (d[i]<mn){
mn=d[i];
r=i;
}
}
location[r]=first+mn;
bs[first]=1;
bs[first+mn]=1;
stype[r]=2;
for (int i=1;i<N;i++)
if (i!=r)
ve.emplace_back(d[i],i);
sort(ve.begin(),ve.end());
vl.push_back(-first);
for (auto [dist,i]:ve){
int x=getDistance(l,i),y=getDistance(r,i);
int a=location[l]+x,b=location[r]-y;
bool ch=0;
if (bs[a])
ch=1;
if (a>first&&a<first+mn)
ch=1;
else
ch|=(location[r]+a+vl[lower_bound(vl.begin(),vl.end(),-a)-vl.begin()]*2!=y);
if (ch){
location[i]=b;
bs[b]=1;
stype[i]=1;
if (location[i]<location[l]){
l=i;
vl.push_back(-b);
}
continue;
}
location[i]=a;
bs[a]=1;
stype[i]=2;
if (location[i]>location[r])
r=i;
}
}
