#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
int min_cardinality(int N){
int uniques = 1;
move_inside(0);
vector uni = {0};
for(int i=1;i<N;i++) {
move_inside(i);
if(press_button()==1){ uniques++;uni.emplace_back(i);}
else move_outside(i);
}
vector<int> last_added;
vector<int> last_removed;
vector<bool> currently(N);
vector<bool> skipped(N);
for(int&i:uni) {
currently[i]=true;
}
auto check = [&](int x) {
last_added.clear();
last_removed.clear();
int curr = 0;
for(int i=0;i<N;i++)if(currently[i])curr++;
for(int i=0;i<N;i++) {
if(currently[i])continue;
if(skipped[i])continue;
currently[i]=true;
move_inside(i);
if(press_button()<=x) {
last_added.emplace_back(i);
if(++curr==uniques*x)return true;
continue;
}
last_removed.emplace_back(i);
move_outside(i);
currently[i]=false;
}
return curr==uniques*x;
};
auto revert = [&]() {
for(int&i:last_added) {
currently[i]=false;
move_outside(i);
}
for(int&i:last_removed)skipped[i]=true;
};
int ans = 0;
int L = 1;
int R = N/uniques;
while(L<=R) {
int mid = (L+R)/2;
if(check(mid)) {
ans=mid;
L = mid+1;
} else {
revert();
R = mid-1;
}
}
return ans;
}
