#include<bits/stdc++.h>
#include "rail.h"
#define MAXN 1000007
using namespace std;
const int inf=1e7;
int n,pos,fr;
pair<int,int> block[MAXN];
pair<int,int> dist[5007];
int last;
vector<int> clos,opos;
int sum[MAXN];
int loc[MAXN];
vector< pair<int,int> > know;
int distan(int x,int y,int xx,int yy){
if(y!=yy){
if(y==1 and yy==2){
if(x<xx)return xx-x;
pair<int,int> news={inf,0};
for(pair<int,int> s:know){
if(s.first>x and s.second==2 and s.first<news.first){
news=s;
}
}
return distan(news.first,news.second,xx,yy)+abs(news.first-x);
}else{
if(x>xx)return x-xx;
pair<int,int> news={-2,0};
for(pair<int,int> s:know){
if(s.first<x and s.second==1 and s.first>news.first){
news=s;
}
}
return distan(news.first,news.second,xx,yy)+abs(news.first-x);
}
}else{
if(y==1 and yy==1){
if(x>xx)swap(x,xx);
pair<int,int> news={inf,0};
for(pair<int,int> s:know){
if(s.first>xx and s.second==2 and s.first<news.first){
news=s;
}
}
return distan(news.first,news.second,xx,yy)+abs(news.first-x);
}else{
if(x>xx)swap(x,xx);
pair<int,int> news={-2,0};
for(pair<int,int> s:know){
if(s.first<x and s.second==1 and s.first>news.first){
news=s;
}
}
return distan(news.first,news.second,xx,yy)+abs(news.first-x);
}
}
}
bool check(int pos,int st,int d1,int d2){
int s1=distan(pos,st,loc[dist[last].second],2);
int s2=distan(pos,st,loc[dist[fr].second],1);
return s1==d1 and s2==d2;
}
void findLocation(int N, int first, int location[], int stype[]){
n=N;
loc[0]=first;
stype[0]=1;
know.push_back({first,1});
for(int i=1;i<n;i++){
dist[i].first=getDistance(0,i);
dist[i].second=i;
}
sort(dist+1,dist+n);
last=1; fr=0;
loc[dist[1].second]=first+dist[1].first;
stype[dist[1].second]=2;
know.push_back({loc[dist[1].second],2});
clos.push_back(1);
opos.push_back(0);
for(int i=2;i<n;i++){
int curr=getDistance(dist[i].second,dist[last].second);
int where=loc[dist[last].second]-curr;
int curr2=getDistance(dist[i].second,dist[fr].second);
int where2=loc[dist[fr].second]+curr2;
if(check(where,1,curr,curr2)){
loc[dist[i].second]=where;
stype[dist[i].second]=1;
}else if(true){
loc[dist[i].second]=where2;
stype[dist[i].second]=2;
}else{
cout<<"failed\n";
}
if(loc[dist[i].second]>loc[dist[last].second]){
last=i;
clos.push_back(i);
}
if(loc[dist[i].second]<loc[dist[fr].second]){
fr=i;
opos.push_back(i);
}
know.push_back({loc[dist[i].second],stype[dist[i].second]});
}
for(int i=0;i<n;i++){
location[i]=loc[i];
}
return;
}
/*
3
8
1 0
2 2
1 3
2 5
2 6
1 7
1 8
2 10
*/
