#include "routers.h"
#include<bits/stdc++.h>
using namespace std;
int lim;
namespace sub12{
vector<int>solve(int n){
vector<int>ans(n);
ans[0] = 0;
for(int i = 1, cnt = 1, id = 1; i <= lim; i++){
if(use_detector(i) == id){
i = ans[id] = ans[id - 1] + ((cnt - 1) << 1);
cnt = 0;
id++;
}
cnt++;
}
return ans;
}
}
namespace sub3{
vector<int>solve(int n){
int low = 0, high = lim, pos;
while(low <= high){
int mid = (low + high) >> 1;
if(use_detector(mid) == 0){
low = (pos = mid) + 1;
}
else{
high = mid - 1;
}
}
return {0, pos << 1};
}
}
namespace sub4{
const int LIM = 1e5 + 1;
int nrid[LIM];
void dnc(int l, int r){
if(nrid[l] == nrid[r]){
fill(nrid + l + 1, nrid + r + 1, nrid[l]);
return;
}
if(l + 1 < r){
int m = (l + r) >> 1;
nrid[m] = use_detector(m);
dnc(l, m);
dnc(m, r);
}
}
vector<int>solve(int n){
memset(nrid, -1, sizeof(nrid));
vector<int>ans(n, 0);
nrid[lim] = n - 1;
dnc(nrid[0] = ans[0] = 0, lim);
for(int i = 1; i < n; i++){
ans[i] = ans[i - 1] + ((lower_bound(nrid, nrid + lim + 1, i) - nrid - 1 - ans[i - 1]) << 1);
}
return ans;
}
}
vector<int>find_routers(int l, int n, int q){
if(q == (lim = l) + 1){
return sub12::solve(n);
}
if(q == 20){
return sub3::solve(n);
}
return sub4::solve(n);
}
