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