#include "insects.h"
#include <bits/stdc++.h>
#define ll long long
#define sz(s) (int)s.size()
#define pb push_back
#define in insert
#define lb lower_bound
#define ub upper_bound
using namespace std;
const int MAX=2e5+10;
vector<int> a;
int cnt[MAX];
set<int> st;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){
return rng()%(r-l+1)+l;
}
void solve(int l,int r,vector<int> b){
if(b.empty())return;
if(l==r){
cnt[l]+=sz(b);
return;
}
int m=rnd(l,r);
while(st.ub(m)!=st.end()&&*st.ub(m)<=r){
move_outside(a[*st.ub(m)]);
st.erase(st.ub(m));
}
vector<int> L,R;
for(int i=l;i<=m;i++){
if(!st.count(i))move_inside(a[i]);
st.in(i);
}
for(int i:b){
move_inside(i);
if(press_button()==2)L.pb(i);
else R.pb(i);
move_outside(i);
}
solve(l,m,L);
solve(m+1,r,R);
}
int min_cardinality(int N){
vector<int> b;
for(int i=0;i<N;i++){
move_inside(i);
if(press_button()==2){
b.pb(i);
move_outside(i);
}
else{
st.in(sz(a));
a.pb(i);
}
}
solve(0,sz(a)-1,b);
int ans=N;
for(int i=0;i<sz(a);i++)ans=min(ans,cnt[i]+1);
return ans;
}
