#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
#define ll long long
const int mod = 1000002022;
vector<int> state, p;
int n, m;
vector<vector<int>> g;
template<typename T>
int len(T &a){return a.size();}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
void shuffle(vector<int> &a, int n){
if(n == 1) return;
random_shuffle(a.begin(), a.begin() + n);
for(int i = 0; i < n; i ++){
int aa = rng() % n, bb = rng() % n;
while(bb == aa) bb = rng() % n;
swap(a[aa], a[bb]);
}
}
int min_cardinality(int n) {
vector<int> cnt(n);
vector<int> type(n);
vector<int> ind(n);
int cur = 0;
for(int i = 0; i < n; i ++){
move_inside(i);
if(press_button() == 1){
type[cur] = i;
ind[cur] = cur;
cnt[cur] ++;
cur ++;
continue;
}
//cout << cur << endl;
shuffle(ind, cur);
int j = cur - 1;
while(j > 0){
move_outside(type[ind[j]]);
if(press_button() == 1){
move_inside(type[ind[j]]);
break;
}
j --;
}
cnt[ind[j]] ++;
while(j + 1 < cur){
j ++;
move_inside(type[ind[j]]);
}
//cout << i << ' ' << ind[j] << endl;
move_outside(i);
}
int ans = n;
for(int i = 0; i < cur; i ++){
ans = min(ans, cnt[i]);
}
return ans;
}
