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