#include "rail.h"
#include <algorithm>
#include <set>
#include <cstdio>
#define INF 1000000000
#define MAXN 5009
int dist[MAXN], perm[MAXN];
std::set < int > C, D;
std::set < int > ::iterator it, it2;
bool cmp(const int &a, const int &b) {
return dist[a] < dist[b];
}
inline bool notFound(int x) {
it = C.lower_bound(x);
if (it != C.end() && *it == x)
return 0;
it = D.lower_bound(x);
if (it != D.end() && *it == x)
return 0;
return 1;
}
inline int myGetDistance(int x, char a, int y, char b) {
if (a == 'C') {
if (b == 'D') {
if (x < y)
return y - x;
it = D.lower_bound(x);
if (it == D.end())
return INF;
it2 = C.lower_bound(y);
if (it2 == C.begin())
return INF;
it2--;
return *it - x + *it - *it2 + y - *it2;
} else {
it = D.lower_bound(std::max(x, y));
if (it == D.end())
return INF;
return *it - x + *it - y;
}
} else if (b == 'C') {
if (x > y)
return x - y;
it = C.lower_bound(x);
if (it == C.begin())
return INF;
it--;
it2 = D.lower_bound(y);
if (it2 == D.end())
return INF;
return x - *it + *it2 - *it + *it2 - y;
} else {
it = C.lower_bound(std::min(x, y));
if (it == C.begin())
return INF;
it--;
return x - *it + y - *it;
}
}
inline void solve(int x, int first, int &val, int &tip, int &left, int &right) {
it = D.end();
it--;
int A = *it, B = *(C.begin());
int dA = getDistance(x, right), dB = getDistance(x, left);
int d = B + dB, c = A - dA;
bool okD = (notFound(d) && myGetDistance(A, 'D', d, 'D') == dA && myGetDistance(first, 'C', d, 'D') == dist[x]);
bool okC = (notFound(c) && myGetDistance(B, 'C', c, 'C') == dB && myGetDistance(first, 'C', c, 'C') == dist[x]);
if (okD == 0 && okC == 0)
okD = 1;
if (okD) {
val = d;
tip = 2;
D.insert(val);
it = D.upper_bound(val);
if (it == D.end())
right = x;
} else {
val = c;
tip = 1;
C.insert(val);
it = C.lower_bound(val);
if (it == C.begin())
left = x;
}
}
void findLocation(int N, int first, int location[], int stype[]) {
location[0] = first;
stype[0] = 1;
for (int i = 1; i < N; i++) {
dist[i] = getDistance(0, i);
perm[i] = i;
}
std::sort(perm + 1, perm + N, cmp);
location[perm[1]] = first + dist[perm[1]];
stype[perm[1]] = 2;
C.insert(first);
D.insert(location[perm[1]]);
int left = 0, right = perm[1];
for (int i = 2; i < N; i++)
solve(perm[i], first, location[perm[i]], stype[perm[i]], left, right);
}
