#include "insects.h"
#include <bits/stdc++.h>
#define ll long long
#define dbg(x) cerr<<#x<<' '<<x<<endl;
using namespace std;
int min_cardinality(int N) {
ll cnt=0;
ll n=N;
vector<ll> insects(N);
iota(insects.begin(), insects.end(),0);
vector<ll> nev;
vector<ll> goodpeople;
for (int i=0;i<n;i++)
{
move_inside(i);
if(press_button() > 1)
{
move_outside(i);
nev.push_back(i);
}
else
{
goodpeople.push_back(i);
cnt++;
}
}
for (auto &&e : goodpeople)
{
move_outside(e);
}
insects=nev;
ll sz=insects.size();
ll ans=1;
while(sz>=cnt)
{
vector<ll> good;
vector<ll> bad;
ll r=sz/cnt;
ll mid=(r+1)/2;
for (int i=0;i<insects.size();i++)
{
ll e=insects[i];
move_inside(e);
if(press_button() > mid)
{
bad.push_back(e);
move_outside(e);
}
else
{
good.push_back(e);
}
if(good.size()==mid*cnt)
{
i++;
for (;i<insects.size();i++)
{
bad.push_back(insects[i]);
}
}
}
if(good.size()==mid*cnt)
{
ans+=mid;
insects=bad;
}
else
{
insects=good;
}
sz=insects.size();
for (auto &&e : good)
{
move_outside(e);
}
}
return ans;
}
