#include <bits/stdc++.h>
#include "rail.h"
#define F first
#define S second
using namespace std;
constexpr int m = 1e6;
vector<int> typeOnBlock(m);
void C(int n, int c, int d, int dn, int location[], int stype[]){
location[n] = location[d] - dn;
stype[n] = 1; // C
typeOnBlock.at(location[n]) = stype[n];
if(dn > d - c) c = n;
}
void D(int n, int c, int d, int cn, int location[], int stype[]){
location[n] = location[c] + cn;
stype[n] = 2; // D
typeOnBlock.at(location[n]) = stype[n];
if(cn > d - c) d = n;
}
void findLocation(int N, int first, int location[], int stype[])
{
// id, distance
vector<pair<int, int>> v(N - 1);
for(int i = 1; i < N; ++i) v.at(i - 1) = {i, getDistance(0, i)};
sort(v.begin(), v.end(), [](const auto& a, const auto& b){
return a.S < b.S;
});
int c = 0;
location[c] = first;
stype[c] = 1;
int d = v.at(0).F;
location[d] = location[c] + v.at(0).S;
stype[d] = 2;
for(int i = 1; i < v.size(); ++i){
int n = v.at(i).F;
int cn = getDistance(c, n);
int dn = getDistance(d, n);
if(cn < dn) D(n, c, d, cn, location, stype);
else if(cn > dn) C(n, c, d, dn, location, stype);
else{
// int cd = getDistance(c, d);
// int nc = getDistance(n, c);
// if(cd + dn == nc)
int mid = (d + c) / 2;
if(typeOnBlock.at(mid) == 2) C(n, c, d, dn, location, stype);
else D(n, c, d, cn, location, stype);
// int type = 0;
// for(int j = i - 1; j >=0; --j) if(v.at(j).F == mid) type = stype[v.at(j).F];
// if(type == 1){
// location[v.at(i).F] = location[c] + cn;
// stype[v.at(i).F] = 2; // D
// if(cn > d - c) d = v.at(i).F;
// }
// else{
// location[v.at(i).F] = location[d] - dn;
// stype[v.at(i).F] = 1; // C
// if(dn > d - c) c = v.at(i).F;
// }
}
}
return;
}
