#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
int min_cardinality(int N) {
int type = 0;
int c = 0;
vector<int> c1;
vector<int> c2;
c1.assign(N,0);
for (int i = 0;i<N;i++){
move_inside(i);
if (press_button()==1){type++;c1[i] = 1;}
else move_outside(i);
}
int a=1;
int b=N;
while (a<b){
vector<int> x2;
int x = (a+b)/2;
int x1 = -1;
for (int i = 0;i<N;i++){
if (c1[i]==1) continue;
move_inside(i);
x1 = press_button();
c++;
if (x1>x){
move_outside(i);
c--;
x2.push_back(i);
}
else c2.push_back(i);
}
if (x*type==c){
a = x+1;
}
else{
b = x-1;
for (int i = 0;i<c2.size();i++) move_outside(c2[i]);
c2.clear();
for (int i = 0;i<x2.size();i++) c1[x2[i]] = 1;
}
}
return b+1;
}
