#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
int min_cardinality(int n) {
//Some very simple idea
vector<int> distinct;
for(int i = 0; i < n; i++){
move_inside(i);
if(press_button() > 1) move_outside(i);
else distinct.push_back(i);
}
for(int i : distinct) move_outside(i);
//Now find the answer
int sz = distinct.size();
vector<int> cur;
for(int i = 0; i < n; i++) cur.push_back(i);
while(true){
int val = cur.size() / sz;
vector<int> good, trash;
for(int i : cur){
move_inside(i);
if(press_button() > val){
move_outside(i); trash.push_back(i);
}
else good.push_back(i);
}
if(trash.size() == 0) return val; //This must happen
//Now remove the bad part
vector<int> qualify;
for(int i : good) move_outside(i);
distinct.clear();
for(int i : trash){
move_inside(i);
if(press_button() > 1) move_outside(i);
else{distinct.push_back(i); sz--;}
}
for(int i : good){
move_inside(i);
if(press_button() > 1) move_outside(i);
else{
distinct.push_back(i); qualify.push_back(i);
}
}
//Reset
for(int i : distinct) move_outside(i);
cur = qualify;
}
}
