#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
struct insect {
int i,sz;
};
vector<insect> types;
int min_cardinality(int N) {
types.push_back(insect{0, 1});
move_inside(0);
vector<bool> skip(N);
int boxSz=1;
for (int i = 1; i < N; i++)
{
move_inside(i);
if(press_button()==1){
types.push_back(insect{i, 1});
boxSz++;
} else{
int l=0, r=boxSz-1;
while(r-l>0){
int mid=(l+r)/2;
for (int j = mid+1; j <= r; j++) move_outside(types[j].i);
if(press_button()>1){
r=mid;
}else{
l=mid+1;
for (int j = mid+1; j <= r; j++) move_inside(types[j].i);
for (int j = l; j <= mid; j++) move_outside(types[j].i);
}
}
types[l].sz++;
move_outside(l);
move_outside(i);
for (int j = 0; j < (int)types.size(); j++) move_inside(types[j].i);
}
}
int mn=1e9;
for (int j = 0; j < (int)types.size(); j++) mn=min(mn,types[j].sz);
return mn;
}
