#include "routers.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
///last[x] <= last[x + 1]
vector<int> p;
int n;
int last[100005];
/*int use_detector(int x)
{
vector<int>::iterator left, right;
right = upper_bound(p.begin(), p.end(), x);
left = prev(right);
if (right == p.end()) {
return n - 1;
} else if ((x - *left) <= (*right - x)){
return distance(p.begin(), left);
} else {
return distance(p.begin(), right);
}
}*/
int caut(int ind, int st, int dr)
{
int sol = 0;
while (st <= dr)
{
int mid = (st + dr) / 2;
int r = use_detector(mid);
if (r < ind)
st = mid + 1;
else
if (r > ind)
dr = mid - 1;
else
{
sol = mid;
st = mid + 1;
}
}
return sol;
}
void divide(int l, int r, int ql, int qr)
{
if (l > r)
return;
int mid = (l + r) / 2;
last[mid] = caut(mid, ql, qr);
divide(l, mid - 1, ql, last[mid] - 1);
divide(mid + 1, r, last[mid] + 1, qr);
}
vector<int> find_routers(int l, int n, int q)
{
divide(0, n - 2, 0, l);
vector <int> ans(n);
ans[0] = 0;
for (int i = 1; i < n; i++)
ans[i] = 2 * last[i - 1] - ans[i - 1];
return ans;
}/*
int main()
{
int l, q;
cin >> l >> n >> q;
p.resize(n);
for (int i = 0; i < n; i++)
cin >> p[i];
vector <int> ans = find_routers(l, n, q);
for (int i = 0; i < n; i++)
cout << ans[i] << " ";
return 0;
}*/
