#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N)
{
int num_insects = 0;
set<int> s;
for(int i = 0; i < N; i++)
{
// cout << "moving inside[1]: " << i << endl;
move_inside(i);
s.insert(i);
num_insects++;
if(press_button() == 2)
{
// cout << "moving outside[1]: " << i << endl;
move_outside(i);
s.erase(i);
num_insects--;
}
}
// cout << "num_insects = " << num_insects << endl;
int l = 1, r = (N + num_insects - 1) / num_insects, ans = r;
while(l <= r)
{
int mid = (l + r) / 2;
// cout << "mid = " << mid << endl;
// cout << "s.size() = " << s.size() << endl;
for(auto i: s)
{
// cout << "i = " << i << endl;
// cout << "moving outside[2]: " << i << endl;
move_outside(i);
}
s.clear();
// cout << "hello!" << endl;
int current_insects = 0;
for(int i = 0; i < N; i++)
{
// cout << "moving inside[3]: " << i << endl;
move_inside(i);
s.insert(i);
current_insects++;
if(press_button() > mid)
{
// cout << "moving outside[3]: " << i << endl;
move_outside(i);
s.erase(i);
current_insects--;
}
}
// cout << "current_insects = " << current_insects << endl;
if(current_insects == mid * num_insects)
{
ans = mid;
l = mid + 1;
}
else
{
r = mid - 1;
}
}
return ans;
}
