#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;
set <int> sl,sr;
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());
sl.insert(-first);
sr.insert(first+mn);
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 (a<0||bs[a])
ch=1;
if (a>first&&a<first+mn)
ch=1;
else if (a<first)
ch|=(location[r]+a+*sl.lower_bound(-a)*2!=y);
else if (b>=0&&!bs[b]){
if (b>first)
ch=(*sr.lower_bound(b)*2-location[l]-b==x);
else
ch=(y-dist==location[r]-first-mn*2);
}
if (ch){
location[i]=b;
bs[b]=1;
stype[i]=1;
if (location[i]<location[l]){
l=i;
sl.insert(-b);
}
continue;
}
location[i]=a;
bs[a]=1;
stype[i]=2;
if (location[i]>location[r]){
r=i;
sr.insert(a);
}
}
}
