#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
vector<int> vec;
bool isFirst[2002];
int type[2002], cnt[2002];
bool inside[2002];
void dnc(int l, int r, vector<int> &candidates){
if(l==r){
for(auto x: candidates) type[x] = vec[l];
return;
}
int m = (l+r)/2;
for(int i=l; i<=m; i++) if(!inside[vec[i]]) inside[vec[i]] = 1, move_inside(vec[i]);
for(int i=m+1; i<=r; i++) if(inside[vec[i]]) inside[vec[i]] = 0, move_outside(vec[i]);
vector<int> vecL, vecR;
for(auto x: candidates){
move_inside(x);
if(press_button() == 2) vecL.push_back(x);
else vecR.push_back(x);
move_outside(x);
}
dnc(l, m, vecL);
dnc(m+1, r, vecR);
}
int min_cardinality(int N){
n = N;
/// 종류 알아내기
for(int i=0; i<n; i++){
move_inside(i);
if(press_button() == 2) move_outside(i);
else vec.push_back(i), isFirst[i] = 1, inside[i] = 1, type[i] = i;
}
/// dnc 하기
k = (int)vec.size();
vector<int> notFirst;
for(int i=0; i<n; i++) if(!isFirst[i]) notFirst.push_back(i);
dnc(0, k-1, notFirst);
for(int i=0; i<n; i++) cnt[type[i]]++;
int ans = INT_MAX;
for(int i=0; i<n; i++) ans = min(ans, cnt[type[i]]);
return ans;
}
