#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 5e3 + 5, INF = 1e9;
int n;
int pos[MAX_N], type[MAX_N];
int dist0[MAX_N];
void init() {
for (int i = 0; i < n; i++) {
pos[i] = type[i] = -1;
dist0[i] = 0;
}
}
set<pii> ups; // Right of 0
set<pii> downs; // Left of 0
bool try_down(int i) {
if (ups.empty()) return false;
int f = ups.rbegin()->second;
int dist = getDistance(i, f);
int new_pos = pos[f] - dist;
assert(ups.upper_bound({new_pos, INF}) != ups.end());
int j = ups.upper_bound({new_pos, INF})->second;
// cout << i << " " << j << endl;
if (dist0[j] + getDistance(j, i) != dist0[i]) return false;
type[i] = 1, pos[i] = new_pos;
if (pos[i] < pos[0]) downs.insert({pos[i], i});
return true;
}
bool try_up(int i) {
if (downs.empty()) return false;
int s = downs.begin()->second;
int dist = getDistance(i, s);
// cout << i << " " << s << endl;
int new_pos = pos[s] + dist;
if (downs.upper_bound({new_pos, INF}) == downs.begin()) return false;
int j = next(downs.upper_bound({new_pos, INF}), -1)->second;
if (dist0[j] + getDistance(j, i) != dist0[i]) return false;
type[i] = 2, pos[i] = new_pos;
return true;
}
void comp() {
vector<pii> ord;
for (int i = 1; i < n; i++) ord.push_back({dist0[i], i});
sort(ord.begin(), ord.end());
for (pii x : ord) {
int i = x.second;
// cout << dist0[i] << " " << i << endl;
if (try_up(i)) continue;
if (try_down(i)) continue;
type[i] = 2, pos[i] = pos[0] + dist0[i];
ups.insert({pos[i], i});
}
}
void findLocation(int tmp_n, int tmp_pos0, int tmp_pos[], int tmp_type[]) {
n = tmp_n;
init();
pos[0] = tmp_pos0, type[0] = 1;
for (int i = 1; i < n; i++) dist0[i] = getDistance(0, i);
comp();
for (int i = 0; i < n; i++) {
tmp_pos[i] = pos[i], tmp_type[i] = type[i];
}
for (int i = 0; i < n; i++) {
// cout << i << ": " << dist0[i] << endl;
// cout << i << ": " << type[i] << " " << pos[i] << endl;
}
}
