#include "routers.h"
#include "bits/stdc++.h"
using namespace std;
map<int, int> mp;
int ask(int x) {
if (mp.count(x)) return mp[x];
return mp[x] = use_detector(x);
}
std::vector<int> find_routers(int l, int n, int q) {
vector<tuple<int, int, int>> v;
vector<bool> used(n);
int last = 0;
for (int i = 0; i < n - 1; i++) {
set<int> st;
for (auto it: mp) {
if (it.first >= last) st.insert(it.second);
}
int exp;
if (st.size() == n - i) {
for (auto it: mp) {
if (it.first < last) continue;
exp = it.second;
break;
}
} else exp = i == 0 ? 0 : ask(last);
int lx = last + 1, rx = l - (n - i - 1), best = last;
for (auto it: mp) {
if (it.second == exp) lx = it.first + 1;
if (it.first < last or it.second == exp) continue;
rx = it.first - 1;
break;
}
best = lx - 1;
while (lx <= rx) {
int mid = (lx + rx) >> 1;
if (ask(mid) == exp) {
best = mid;
lx = mid + 1;
} else {
rx = mid - 1;
}
}
used[exp] = true;
v.emplace_back(exp, last, best);
last = best + 1;
}
for (int i = 0; i < n; i++) {
if (!used[i]) v.emplace_back(i, last, l);
}
vector<int> ans(n);
for (int i = 1; i < n; i++) {
auto [a, b] = make_pair(get<0>(v[i - 1]), get<0>(v[i]));
int start = ans[a], mid = get<2>(v[i - 1]);
// cout << a << ' ' << b << ' ' << start << ' ' << mid << endl;
if (a > b) mid++;
ans[b] = mid + (mid - start);
// cout << '\t' << ans[b] << endl;
}
return ans;
}
