#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
#define F first
#define S second
#define fast ios::base_sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll vis[10000];
int min_cardinality(int N) {
vector<ll> v;
for(int i = 0; i < N; i++)
{
move_inside(i);
if(press_button()!=1) move_outside(i);
else v.push_back(i);
}
ll cnt = v.sz;
for(int i = 0; i < v.sz; i++) move_outside(v[i]);
v.clear();
//cout << "cnt: " << cnt << endl;
if(cnt<9)
{
set<ll> s;
for(int i = 0; i< N; i++) s.insert(i);
ll mn = N;
for(int times = 0; times < cnt-1; times++)
{
auto it = s.begin();
while(it!=s.end())
{
ll x = *it;
move_inside(x);
if(press_button()!=v.sz+1) move_outside(x), it++;
else{
v.push_back(x);
it = s.erase(it);
}
}
for(int i = 0; i < v.sz; i++) move_outside(v[i]);
//cout << "cur"<< times << " : " << v.sz << endl;
mn = min(mn, (ll)v.sz);
v.clear();
}
//cout << s.sz << endl;
mn = min(mn, (ll)s.sz);
return mn;
}
else
{
ll l = 1, r = N/cnt;
ll mx = -1;
while(l<r)
{
ll mid = r-(r-l)/2;
ll k = 0;
if(mid<mx)
for(int i = N-1; i >= 0; i--)
{
if(vis[i]>mid)
v.pop_back(), move_outside(i), k =i, vis[i] = 0;
}
else
for(int i = N-1; i >= 0; i--)
{
if(vis[i]==mx) v.pop_back(), move_outside(i), k = i,vis[i] = 0;
}
for(int i = k; i < N; i++)
{
move_inside(i);
ll press = press_button();
if(press>mid) move_outside(i),vis[i] = 0;
else v.push_back(i),vis[i] = press;
}
if(cnt * mid == v.sz) l = mid;
else r = mid-1;
mx = mid;
// clear
}
return l;
}
return 0;
}
