#include "rail.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int c,d;
int a[5001],b[5001];
int qc[5001],qd[5001];
int loc[1000001];
vector<int>l,r;
stack<int>s;
bool cmp(int x,int y){
return qc[x]<qc[y];
}
void findLocation(int N, int first, int location[], int stype[]){
n=N;
for(int i=0; i<n ;i++){
a[i]=b[i]=qc[i]=qd[i]=0;
}
l.clear();r.clear();
c=0;a[c]=first;b[c]=1;loc[a[c]]=1;
int d=1;
for(int i=0; i<n ;i++){
if(i!=c) qc[i]=getDistance(c,i);
if(i!=c && qc[i]<qc[d]) d=i;
}
a[d]=a[c]+qc[d];b[d]=2;loc[a[d]]=2;
for(int i=0; i<n ;i++){
if(i==c) qd[i]=qc[d];
else if(i!=d) qd[i]=getDistance(d,i);
if(i!=d && qd[i]<qd[c]) c=i;
}
for(int i=0; i<n ;i++) if(i!=0 && i!=c) qc[i]-=qd[0]-qd[c];
swap(qc[0],qc[c]);
a[c]=a[d]-qd[c];b[c]=1;loc[a[c]]=1;
for(int i=0; i<n ;i++){
if(i==c || i==d) continue;
if(qc[i]>qd[i]) l.push_back(i);
else r.push_back(i);
}
s.push(c);
sort(l.begin(),l.end(),cmp);
for(auto x:l){
if(x==l[0]){
a[x]=a[d]-qd[x];b[x]=1;loc[a[x]]=1;
s.push(x);
continue;
}
int y=s.top();
int dis=getDistance(y,x);
int r=(qd[y]+dis-qd[x])/2+y;
if(loc[r]!=1){
a[x]=a[d]-qd[x];b[x]=1;loc[a[x]]=1;
s.push(x);
}
else{
a[x]=a[y]+dis;b[x]=2;loc[a[x]]=2;
}
}
while(!s.empty()) s.pop();
sort(r.begin(),r.end(),cmp);
s.push(d);
for(auto x:r){
if(x==r[0]){
a[x]=a[c]+qc[x];b[x]=2;loc[a[x]]=2;
s.push(x);
continue;
}
int y=s.top();
int dis=getDistance(y,x);
int r=y-(qc[y]+dis-qc[x])/2;
if(r<0) while(true);
if(loc[r]!=2){
a[x]=a[c]+qc[x];b[x]=2;loc[a[x]]=2;
s.push(x);
}
else{
a[x]=a[y]-dis;b[x]=1;loc[a[x]]=1;
}
}
for(int i=0; i<n ;i++) loc[a[i]]=0;
for(int i=0; i<n ;i++) location[i]=a[i],stype[i]=b[i];
}
