#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int n,br,otg;
vector<int>temp,cur,v;
void get_unique()
{
for(int i=0;i<n;i++)
{
move_inside(i);
br++;
temp.push_back(i);
if(press_button()>1)
{
move_outside(i);
temp.pop_back();
br--;
}
}
for(int i=0;i<br;i++)
{
move_outside(temp[i]);
}
temp.clear();
}
int check(int ma)
{
int num=0;
for(int i=0;i<cur.size();i++)
{
move_inside(cur[i]);
num++;
if(press_button()>ma)
{
temp.push_back(i);
move_outside(cur[i]);
num--;
}
}
cout<<num<<" "<<br<<endl;
if(num/br==ma)return 1;
return 0;
}
void get_min()
{
int l=1,r=n/br,mid;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid))
{
cur=temp;
l=mid+1;
}
else
{
int to=0;
for(int i=0;i<=cur.size();i++)
{
if(to<temp.size()&&cur[i]!=temp[to])
{
v.push_back(cur[i]);
}
else to++;
}
cur=v;
v.clear();
r=mid-1;
}
temp.clear();
/*cout<<l<<" "<<r<<" | ";
for(int i=0;i<cur.size();i++)
{
cout<<cur[i]<<" ";
}
cout<<endl;*/
}
//cout<<endl;
otg=l-1;
}
int min_cardinality(int N)
{
n=N;
get_unique();
if(br==1)return N;
for(int i=1;i<=n;i++)
{
cur.push_back(i-1);
}
get_min();
return otg;
}
