#include "rail.h"
#include <bits/stdc++.h>
#define int long long
const int inf = 1e18;
void findLocation(signed n, signed first, signed location[], signed stype[]){
stype[0] = 1;
location[0] = first;
if (n == 1){
return;
}
int loc0[n], locD[n], locC[n];
std::map<int, int> posToType;
posToType[first] = 1;
int firstD = inf, firstC = inf, distD = inf, distC = inf;
for (int i = 0; i < n; i++){
if (i == 0) loc0[i] = 0;
else{
loc0[i] = getDistance(0, i);
}
}
// sort by least
for (int i = 0; i < n; i++){
if (i == 0) continue;
if (distD > loc0[i]){
distD = loc0[i];
firstD = i;
}
}
for (int i = 0; i < n; i++){
if (i == firstD) locD[i] = 0;
else if (i == 0) locD[i] = loc0[firstD];
else locD[i] = getDistance(firstD, i);
}
// sort by least
for (int i = 0; i < n; i++){
if (i == firstD) continue;
if (distC > locD[i]){
distC = locD[i];
firstC = i;
}
}
// find the distances between each station
stype[firstC] = 1;
stype[firstD] = 2;
location[firstD] = location[0] + distD;
location[firstC] = location[firstD] - distC;
posToType[location[firstC]] = 1;
posToType[location[firstD]] = 2;
// std::cout << "idx: " << firstC << " type: " << stype[firstC] << " location: " << location[firstC] << "\n";
// std::cout << "idx: " << firstD << " type: " << stype[firstD] << " location: " << location[firstD] << "\n";
// std::cout << "idx: " << 0 << " type: " << stype[0] << " location: " << location[0] << "\n";
locC[firstC] = 0;
for (int i = 0; i < n; i++){
if (locD[i] == loc0[i] - distD){
// then its before D
locC[i] = locD[i] + distC;
}
else{
// then its after D
locC[i] = locD[i] - distC;
}
}
std::vector<int> l, r;
std::vector<std::pair<int, int>> C(n), D(n);
for (int i = 0; i < n; i++){
if (i == firstC || i == firstD || i == 0) continue;
if (locC[i] > locD[i]){
l.push_back(i);
}
else{
r.push_back(i);
}
}
// std::cout << "l: ";
// for (int i: l){
// std::cout << i << ' ';
// }
// std::cout << "\n";
// std::cout << "r: ";
// for (int i: r){
// std::cout << i << ' ';
// }
// std::cout << "\n";
for (int i = 0; i < n; i++){
C[i] = {locC[i], i};
D[i] = {locD[i], i};
}
std::sort(C.begin(), C.end());
std::sort(D.begin(), D.end());
// for (int i = 0; i < n; i++){
// std::cout << C[i].first << ' ' << C[i].second << std::endl;
// }
// for (int i = 0; i < n; i++){
// std::cout << D[i].first << ' ' << D[i].second << std::endl;
// }
int furthestD = firstD, furthestC = firstC;
// std::cout << furthestD << "\n";
// consider left bound
for (int i = 1; i < n; i++){
std::pair<int, int> pa = D[i];
int idx = pa.second, ok = 0;
for (int j: l){
if (idx == j){
ok = 1;
break;
}
}
if (!ok) continue;
int distfromC = getDistance(furthestC, idx);
int minus = pa.first - distfromC;
int sum = location[firstD] - location[furthestC];
int mysteriousLocation = location[firstD] - (sum + minus)/2;
if ((posToType.find(mysteriousLocation) == posToType.end() || posToType[mysteriousLocation] != 1) && (pa.first != distfromC + sum)) {
stype[idx] = 1;
location[idx] = location[firstD] - pa.first;
posToType[location[idx]] = 1;
furthestC = idx;
// std::cout << "idx: " << idx << " type: " << stype[idx] << " location: " << location[idx] << "\n";
}
else{
stype[idx] = 2;
location[idx] = location[furthestC] + distfromC;
posToType[location[idx]] = 2;
// std::cout << "idx: " << idx << " type: " << stype[idx] << " location: " << location[idx] << "\n";
}
}
furthestD = firstD, furthestC = firstC;
// std::cout << furthestD << "\n";
// consider left bound
for (int i = 1; i < n; i++){
std::pair<int, int> pa = C[i];
int idx = pa.second, ok = 0;
for (int j: r){
if (idx == j){
ok = 1;
break;
}
}
if (!ok) continue;
int distfromD = getDistance(furthestD, idx);
int minus = pa.first - distfromD;
int sum = location[furthestD] - location[firstC];
int mysteriousLocation = (minus + sum)/2 + location[firstC];
if ((posToType.find(mysteriousLocation) == posToType.end() || posToType[mysteriousLocation] != 2) && (pa.first != distfromD + sum)) {
stype[idx] = 2;
location[idx] = location[firstC] + pa.first;
posToType[location[idx]] = 2;
furthestD = idx;
// std::cout << "idx: " << idx << " type: " << stype[idx] << " location: " << location[idx] << "\n";
}
else{
stype[idx] = 1;
location[idx] = location[furthestD] - distfromD;
posToType[location[idx]] = 1;
// std::cout << "idx: " << idx << " type: " << stype[idx] << " location: " << location[idx] << "\n";
}
}
}
