#include <iostream>
#include <vector>
#include <algorithm>
#include "rail.h"
using namespace std;
int dis1[10000];
int sp;
int dis2[10000];
int sta[10000];
int mnd;
int cntd;
int cntc;
int conc[10000];
int cond[10000];
struct pla{
int x, y;
};
vector<pla> lef;
vector<pla> rig;
bool cmp1(const pla &a, const pla &b){
return a.y > b.y;
}
bool cmp2(const pla &a, const pla &b){
return a.y < b.y;
}
int getDistance(int i, int j);
void findLocation(int n, int first, int location[], int stype[]){
location[0] = first;
stype[0]=1;
sp = 0;
sta[0] = 2;
mnd = 100000000;
cntc=0;
cntd=0;
cntc++;
conc[1] = first;
for(int i=1; i<n; i++){
dis1[i] = getDistance(0, i);
if(dis1[i]<mnd){sp = i; mnd = dis1[i];}
}
location[sp] = first + dis1[sp];
stype[sp]=2;
sta[sp] = 2;
cntd++;
cond[1] = location[sp];
mnd = 100000000;
for(int i=1; i<n; i++){
if(i!=sp){
dis2[i] = getDistance(sp, i);
if(dis1[i] == dis2[i] + dis1[sp]){
if(dis2[i]<dis1[sp]){sta[i] = 2; location[i] = location[sp] - dis2[i]; stype[i] = 1;
cntc++; conc[cntc] = location[i];
}
else {sta[i] = 1;}
}
else {sta[i] = 3;}
}
}
for(int i=1; i<n; i++){
if(sta[i]==1){
lef.push_back({i, dis2[i]});
}
if(sta[i]==3){
rig.push_back({i, dis1[i]});
}
}
sort(rig.begin(), rig.end(), cmp2);
sort(lef.begin(), lef.end(), cmp2);
int cur = sp;
for(const auto &inf : rig){
int n1 = inf.x;
int n2 = inf.y;
if(cur==sp){
location[n1] = first + n2;
stype[n1] = 2;
cur = n1;
cntd++; cond[cntd] = location[n1];
}
else {
int n3 = getDistance(cur, n1);
int n4 = location[cur] - n3;
int n5 = 100000000;
for(int i=1; i<=cntd; i++){
if(cond[i] > n4){ n5 = min(n5, cond[i]);}
}
if(n2 == 2*n5 - n4 - first){
location[n1] = location[cur] - n3;
stype[n1] = 1;
cntc++;
conc[cntc] = location[n1];
}
else {
location[n1] = first + n2;
stype[n1] = 2;
cur = n1;
cntd++;
cond[cntd] = location[n1];
}
}
}
cur = 0;
for(const auto &inf : lef){
int n1 = inf.x;
int n2 = inf.y;
if(cur==0){
location[n1] = location[sp] - n2;
stype[n1] = 1;
cur = n1;
cntc++; conc[cntc] = location[n1];
}
else {
int n3 = getDistance(cur, n1);
int n4 = location[cur] + n3;
int n5 = 0;
for(int i=1; i<=cntc; i++){
if(conc[i] < n4){ n5 = max(n5, conc[i]);}
}
if(n2 == n4 + location[sp] - 2*n5){
location[n1] = n4;
stype[n1] = 2;
cntd++; cond[cntd] = location[n1];
}
else {
location[n1] = location[sp] - n2;
stype[n1] = 1;
cur = n1;
cntc++;
conc[cntc] = location[n1];
}
}
}
}
