#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<pii> vii;
void findLocation(int n, int first, int location[], int stype[])
{
location[0] = first;
stype[0] = 1;
vii seq;
FOR(i, 1, n-1) {
int d = getDistance(0, i);
seq.pb({d, i});
}
sort(seq.begin(), seq.end());
int le = 0, ri = seq[0].s;
stype[ri] = 2;
location[ri] = first + seq[0].f;
FOR(i, 1, (int)seq.size()-1) {
int id = seq[i].s;
int d1 = getDistance(le, id);
int d2 = getDistance(ri, id);
if (d1 < d2) {
location[id] = location[le] + d1;
stype[id] = 2;
} else {
location[id] = location[ri] - d2;
stype[id] = 1;
}
if (location[id] < location[le]) le = id;
if (location[id] > location[ri]) ri = id;
}
/*FOR(i, 0, n-1) {
cout << " i = " << i << " location = " << location[i] << " stype = " << stype[i] << endl;
}*/
}
/*
1
4
1 1
2 4
2 7
2 9
2
6
1 3
2 6
2 7
1 1
1 0
2 8
*/
