#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
int n;
//int getDistance(int i, int j);
void findLocation(int N, int first, int location[], int stype[]){
//1: lhs (up-down)
//2: rhs (down-up)
n=N;
location[0]=first;
stype[0]=1;
if (n==1){
return;
}
vector<pair<int,int>> distfrom0(n);
distfrom0[0]={0,0};
for (int i = 1; i<n; i++){
distfrom0[i]={getDistance(0,i),i};
}
sort(distfrom0.begin(),distfrom0.end());
//last c, first d
int indlastc = 0;
int indfirstd = distfrom0[1].second;
//cout<<indlastc<<" "<<indfirstd<<'\n';
stype[indfirstd]=2;
location[indfirstd]=first+distfrom0[1].first;
for (int i = 2; i<n; i++){
int ind = distfrom0[i].second;
//cout<<i<<": "<<ind<<'\n';
int distc = getDistance(indlastc,ind);
int distd = getDistance(indfirstd,ind);
if (distc>distd){
location[ind]=location[indfirstd]-distd;
stype[ind]=1;
} else {
location[ind]=location[indlastc]+distc;
stype[ind]=2;
}
}
/*for (int i = 0; i<n; i++){
cout<<stype[i]<<" "<<location[i]<<'\n';
}*/
return;
}
