#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int n, tc, il, rc = 0;
set<int> M, IU;
void mi(int i) {
move_inside(i);
M.insert(i);
}
void mo(int i) {
move_outside(i);
M.erase(i);
}
int pb() {
return press_button()+rc;
}
void rm(bool t) {
if(t) {
for(auto x : M) {
IU.erase(x);
move_outside(x);
}
il -= M.size();
rc += M.size()/tc;
M.clear();
}
else {
IU = M;
il = M.size();
for(auto x : M)
move_outside(x);
M.clear();
}
}
bool tjek(int g) {
for(auto i : IU) {
mi(i);
if(pb() > g) mo(i);
}
bool s = (int(M.size())+rc*tc == tc*g);
rm(s);
return s;
}
int min_cardinality(int N) {
il = n = N; mi(0);
for(int i = 1; i < n; i++) {
mi(i);
if(pb() > 1) mo(i);
}
tc = M.size();
for(int i = 0; i < n; i++)
IU.insert(i);
rm(1);
int l = 1, u = n/tc;
while(l < u) {
int g = (l+u+1)/2;
if(tjek(g)) l = g;
else u = g-1;
}
return l;
}
