#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int cnt[N];
vector <int> rep;
set <int> simulate;
void moveinside(int pos){
if(simulate.find(pos) != simulate.end())
return;
simulate.insert(pos);
move_inside(pos);
}
void moveoutside(int pos){
if(simulate.find(pos) == simulate.end())
return;
simulate.erase(pos);
move_outside(pos);
}
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 = l;i <= mid;i++){
moveinside(rep[i]);
}
for(int i = mid+1;i <= r;i++){
moveoutside(rep[i]);
}
for(auto x : ask){
moveinside(x);
int val = press_button();
moveoutside(x);
if(val > 1) v1.push_back(x);
else v2.push_back(x);
}
if(v1.size() < v2.size()){
solve(l, mid, v1);
solve(mid+1, r, v2);
}
else{
solve(mid+1, r, v2);
solve(l, mid, v1);
}
return;
}
int min_cardinality(int n) {
srand(time(0));
rep.push_back(0);
moveinside(0);
vector <int> at;
for(int i = 1;i < n;i++){
moveinside(i);
int v = press_button();
if(v > 1) {
moveoutside(i);
at.push_back(i);
}
else{
rep.push_back(i);
}
}
random_shuffle(rep.begin(), rep.end());
solve(0, rep.size()-1,at);
int ans = 1e9;
for(auto x : rep){
//cout << cnt[x] << ' ';
ans = min(ans, cnt[x]);
}
return ans;
}
