#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define maxn 2005
#define pf printf
int num[maxn];
vector<int> uni,multi,query[maxn];
deque<pair<int,int>> dq,dq2;
int min_cardinality(int N){
for(int i=0;i<N;++i){
move_inside(i);
if(press_button()==1)uni.push_back(i);
else move_outside(i),multi.push_back(i);
}
int direction=0;
int n=uni.size();
for(int x:multi)query[0].push_back(x);
dq.push_back({0,n-1});
int cur=n-1;
//pf("uni: ");for(int i:uni)pf("%d ",i);pf("\n");
//pf("multi: ");for(int i:multi)pf("%d ",i);pf("\n");
while(!dq.empty()){
int l,r;
if(direction==0){//backwards
tie(l,r)=dq.back();
dq.pop_back();
}
else{//forwards
tie(l,r)=dq.front();
dq.pop_front();
}
//pf("query %d %d: ",l,r);
//for(int x:query[l])pf("%d ",x);
//pf("\n");
if(l==r){
for(int x:query[l])++num[l];
continue;
}
int m=(l+r)>>1;
while(cur<m)move_inside(uni[++cur]);
while(m<cur)move_outside(uni[cur--]);
vector<int> tl,tr;
for(int x:query[l]){
move_inside(x);
if(press_button()==2)tl.push_back(x);
else tr.push_back(x);
move_outside(x);
}
if(direction==0){//backwards
if(!tr.empty()){
dq2.push_front({m+1,r});
swap(tr,query[m+1]);
}
if(!tl.empty()){
dq2.push_front({l,m});
swap(tl,query[l]);
}
if(dq.empty()){
direction=1;//forward
swap(dq,dq2);
}
}
else{//forward
if(!tl.empty()){
dq2.push_back({l,m});
swap(tl,query[l]);
}
if(!tr.empty()){
dq2.push_back({m+1,r});
swap(tr,query[m+1]);
}
if(dq.empty()){
direction=0;//backwards
swap(dq,dq2);
}
}
}
int ans=N;
for(int i=0;i<n;++i)ans=min(ans,num[i]+1);
return ans;
}
