#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=5000+5;
int dp[mxn][mxn],color[mxn],dis[mxn],st[mxn],pos[mxn],mx,l,r;
set<int>x,y;
int ask(int i,int j){
if(pos[i]!=-1&&pos[j]!=-1&&st[i]+st[j]==3){
return abs(pos[i]-pos[j]);
}
if(i>j) swap(i,j);
if(i==j) return 0;
if(dp[i][j]) return dp[i][j];
return dp[i][j]=getDistance(i,j);
}
bool check1(int i){
auto it=y.lower_bound(pos[l]);
int m=*it;
int nw=pos[r]-ask(r,i);
if(ask(l,i)==abs(pos[l]-m)+abs(m-nw)){
pos[i]=nw;
st[i]=1;
x.insert(pos[i]);
l=i;
return true;
}
else{
return false;
}
}
bool check2(int i){
auto it=x.upper_bound(pos[r]);
it--;
int m=*it;
int nw=pos[l]+ask(l,i);
if(ask(r,i)==abs(pos[r]-m)+abs(m-nw)){
pos[i]=nw;
st[i]=2;
y.insert(pos[i]);
r=i;
return true;
}
else{
return false;
}
}
bool check3(int i){
int nw=pos[r]-ask(r,i);
auto it=y.lower_bound(nw);
int m=*it;
if(ask(l,i)==abs(nw-m)+abs(m-pos[l])){
pos[i]=nw;
st[i]=1;
x.insert(pos[i]);
return true;
}
else{
return false;
}
}
bool check4(int i){
int nw=pos[l]+ask(l,i);
auto it=x.upper_bound(nw);
it--;
int m=*it;
if(ask(r,i)==abs(pos[r]-m)+abs(m-nw)){
pos[i]=nw;
st[i]=2;
y.insert(pos[i]);
return true;
}
else{
return false;
}
}
void findLocation(int n, int first, int loc[], int stype[])
{
for(int i=0;i<n;i++){
st[i]=-1;
pos[i]=-1;
}
mx=1e5,r=0;
for(int i=1;i<n;i++){
if(ask(0,i)<mx){
mx=ask(0,i);
r=i;
}
}
l=0;
pos[0]=first;
st[0]=1;
pos[r]=first+mx;
st[r]=2;
color[l]=1;
color[r]=1;
x.insert(pos[l]);
y.insert(pos[r]);
vector<pii>vt;
for(int i=0;i<n;i++){
vt.pb({ask(0,i),i});
}
sort(all(vt));
for(int id=0;id<n;id++){
int i=vt[id].S;
if(color[i]) continue;
if(check1(i)){
color[i]=1;
}
else if(check2(i)){
color[i]=1;
}
else if(check3(i)){
color[i]=1;
}
else if(check4(i)){
color[i]=1;
}
}
for(int i=0;i<n;i++){
loc[i]=pos[i];
stype[i]=st[i];
}
}
