#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define ld long double
int n;
void clean(vector<int> &arr) {
for (int i: arr) {
move_outside(i);
}
arr.clear();
}
int min_cardinality(int N) {
int numtype = 0, size = 0;
n = N;
vector<int> curarr;
for (int i=0;i<n;i++) {
move_inside(i);
numtype += 1;
curarr.pb(i);
if (press_button() > 1) {
move_outside(i);
numtype -= 1;
curarr.pop_back();
}
}
if (numtype == 1) return n;
else
clean(curarr);
int top = n + 1, bottom = 1, mid;
if (numtype == 1) return n;
else top = n / 2 + 1;
while (top > bottom + 1) {
mid = (top + bottom) / 2;
for (int i=0;i<n;i++) {
move_inside(i);
curarr.pb(i);
if (press_button() > mid) {
move_outside(i);
curarr.pop_back();
}
}
if (curarr.size() == numtype * mid) {
bottom = mid;
} else {
top = mid;
}
clean(curarr);
}
return bottom;
}
