#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
void findLocation(int N, int first, int location[], int stype[]){
location[0] = first;
stype[0] = 1;
vector<int> dist(N);
for (int i = 1; i < N; i++) dist[i] = getDistance(0, i);
vector<int> perm(N - 1);
iota(perm.begin(), perm.end(), 1);
sort(perm.begin(), perm.end(), [&](int i, int j){
return dist[i] < dist[j];
});
set<int> C, D;
C.insert(first);
int P = perm[0];
perm.erase(perm.begin());
location[P] = first + dist[P];
stype[P] = 2;
D.insert(location[P]);
int L = 0, R = P;
for (int i : perm){
int dL = getDistance(i, L), dR = getDistance(i, R);
int pos = location[L] + dL;
int p = *--C.upper_bound(pos);
if (pos < R && dR == pos - p + location[R] - p){
location[i] = pos;
stype[i] = 2;
D.insert(location[i]);
if (location[i] > location[R]) R = i;
continue;
}
pos = location[L] + dL;
p = *--C.upper_bound(location[R]);
if (pos > R && dR == pos - p + location[R] - p){
location[i] = pos;
stype[i] = 2;
D.insert(location[i]);
if (location[i] > location[R]) R = i;
continue;
}
pos = location[R] - dR;
p = *D.upper_bound(location[L]);
if (pos < L && dL == p - pos + p - location[L]){
location[i] = pos;
stype[i] = 1;
C.insert(location[i]);
if (location[i] < location[L]) L = i;
continue;
}
pos = location[R] - dR;
p = *D.upper_bound(pos);
if (pos > L && dL == p - pos + p - location[L]){
location[i] = pos;
stype[i] = 1;
C.insert(location[i]);
if (location[i] < location[L]) L = i;
continue;
}
}
}
