#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int cnt[N];
vector <int> rep;
void solve(int l, int r, vector <int> ask){
if(l == r){
cnt[rep[l]] = ask.size()+1;
return;
}
vector <int> v1, v2;
int mid = (l+r)/2;
for(int i = mid+1;i <= r;i++){
move_outside(rep[i]);
}
for(auto x : ask){
move_inside(x);
int val = press_button();
move_outside(x);
if(val > 1) v1.push_back(x);
else v2.push_back(x);
}
solve(l, mid, v1);
for(int i = l;i <= r;i++){
if(i <= mid){
move_outside(rep[i]);
}
else{
move_inside(rep[i]);
}
}
solve(mid+1, r, v2);
return;
}
int min_cardinality(int n) {
rep.push_back(0);
move_inside(0);
vector <int> at;
for(int i = 1;i < n;i++){
move_inside(i);
int v = press_button();
if(v > 1) {
move_outside(i);
at.push_back(i);
}
else{
rep.push_back(i);
}
}
solve(0, rep.size()-1,at);
int ans = 1e9;
for(auto x : rep){
//cout << cnt[x] << ' ';
ans = min(ans, cnt[x]);
}
return ans;
}
