#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
int n,t;
int min_cardinality(int N)
{
vector<int> col;
n = N;
for (int i = 0; i < n; i++){
t++;
move_inside(i);
int res = press_button();
if (res > 1){
move_outside(i);
col.push_back(i);
t--;
}
}
if (t == n) return 1;
if (t == 1) return n;
int l = 1, r = n/t;
int pre = t;
int ans = -1;
while (l <= r){
int mid = (l+r+1)/2;
int cnt = pre;
vector<int> ye, no;
//reverse(col.begin(), col.end());
int idx = 0;
for (int x : col){
cnt++;
move_inside(x);
ye.push_back(x);
int res = press_button();
if (res > mid){
cnt--;
ye.pop_back();
no.push_back(x);
move_outside(x);
}
idx++;
if (cnt == mid*t) break;
}
while (idx < (int)col.size()){
no.push_back(col[idx]);
idx++;
}
col.clear();
if (cnt == mid*t){
pre = cnt;
for (int x : no) col.push_back(x);
ans = mid;
l = mid+1;
}
else{
for (int x : ye){
move_outside(x);
col.push_back(x);
}
r = mid-1;
}
}
if (ans == -1) ans = l;
return ans;
}
