#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int n, tc, il, rc = 0;
set<int> M, IU;
vi IS;
void mi(int i) {
move_inside(IS[i]);
M.insert(i);
}
void mo(int i) {
move_outside(IS[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(IS[x]);
}
il -= M.size();
rc += M.size()/tc;
M.clear();
}
else {
IU = M;
il = M.size();
for(auto x : M)
move_outside(IS[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;
IS.resize(n);
for(int i = 0; i < n; i++)
IS[i] = i;
srand(time(NULL));
random_shuffle(IS.begin(), IS.end());
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 mx = -1, g = (l+u+1)/2;
for(int i = l; i <= u; i++) {
if(max(tc*i, il-tc*i+1) > mx)
mx = max(tc*i, il-tc*i+1), g = i;
}
if(tjek(g)) l = g;
else u = g-1;
}
return l;
}
