#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[])
{
typedef pair<int,int> ii;
int n = N;
vector<ii> order;
int zeroDist[n];
zeroDist[0] = 0;
for(int i = 1;i < n;i++){
zeroDist[i] = getDistance(i,0);
order.push_back(ii(zeroDist[i],i));
}
sort(order.begin(),order.end());
int a = order[0].second;
int aDist[n];
aDist[a] = 0;
for(int i = 0;i < n;i++){
if(i == a) continue;
aDist[i] = getDistance(i,a);
}
int dd = order[0].first;
stype[0] = 1;
stype[a] = 2;
location[0] = first;
location[a] = first + dd;
int second = first + dd;
int l = 0;
int r = a;
map<int,int> mm;
mm[first] = 1;
mm[first+dd] = 2;
for(int k = 1;k < (int) order.size();k++){
int u = order[k].second;
//cout << u << "\n";
///left of a
if(zeroDist[u] == aDist[u] + dd){
///corner case, in between 0 and a
if(aDist[u] < dd){
stype[u] = 1;
location[u] = location[a] - aDist[u];
mm[location[u]] = stype[u];
}
///upwards
else{
int kk = getDistance(l,u);
int x = kk - aDist[u] + aDist[l];
x /= 2;
int pos = location[l] + x;
//cout << u << " " << pos << "\n";
if(mm[pos] == 1){
location[u] = location[l] + kk;
stype[u] = 2;
mm[location[u]] = stype[u];
}
else{
location[u] = second - aDist[u];
stype[u] = 1;
mm[location[u]] = stype[u];
l = u;
}
}
}
else{
int kk = getDistance(r,u);
int x = kk - zeroDist[u] + zeroDist[r];
x /= 2;
int pos = location[r] - x;
//cout << u << " " << pos << "\n";
if(mm[pos] == 2){
location[u] = location[r] - kk;
stype[u] = 1;
mm[location[u]] = stype[u];
}
else{
location[u] = first + zeroDist[u];
stype[u] = 2;
mm[location[u]] = stype[u];
r = u;
}
}
}
}
