#include "insects.h"
#include "bits/stdc++.h"
using namespace std;
set<int> machine;
int pvans; // Answer doesn't change if machine doesn't change
int inc = 0, outc = 0, qc = 0;
void move_in(int i) {
if(machine.count(i)) return;
machine.insert(i);
move_inside(i);
inc++;
pvans = -1;
}
void move_out(int i) {
if(machine.count(i)) {
machine.erase(i);
move_outside(i);
outc++;
pvans = -1;
}
}
int query() {
if(pvans == -1) {
qc++;
return pvans = press_button();
}
return pvans;
}
bool in_machine(int i) {
return machine.count(i);
}
int min_cardinality(int N) {
int T = 0;
pvans = -1;
for(int i=0; i<N; i++) {
move_in(i);
int pb = query();
if(pb == 1) {
T++;
}
else {
move_out(i);
}
}
for(int i=0; i<N; i++) {
move_out(i);
}
if(T == 1) return N;
int lb = 1, rb = N/T;
set<int> relevant;
for(int i=0; i<N; i++) relevant.insert(i);
while(lb < rb) {
int mid = lb + (rb - lb) / 1.5;
if(rb - lb <= 2) mid = (lb + rb + 1) >> 1;
int overflow = 0;
int m = relevant.size();
for(int x: relevant) {
move_in(x);
int qans = query();
if(qans > mid) {
move_out(x);
overflow++;
}
}
if(overflow == m - T * mid) {
lb = mid;
}
else {
rb = mid - 1;
relevant.clear();
for(int i=0; i<N; i++) {
if(in_machine(i)) relevant.insert(i);
move_out(i);
}
}
}
return lb;
}
