#include "insects.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 2e3 + 5;
map<vector<int>,int> Cache;
int vis[N], Kill[N] , D , tot = 0;
inline bool Add(int x){
if(vis[x] || Kill[x]) return 0;
vis[x]=1;
tot++;
move_inside(x);
return 1;
}
inline bool Rem(int x){
if(!vis[x] || Kill[x]) return 0;
vis[x]=0;
tot--;
move_outside(x);
return 1;
}
inline int Get(){
vector<int> v;
for(int i=0;i<N;i++) if(vis[i]) v.push_back(i);
if(Cache.count(v)) return Cache[v];
return Cache[v] = press_button();
}
int min_cardinality(int n){
random_device rd;
mt19937 rng(rd());
vector<int> go(n,0);
iota(go.begin(),go.end(),0);
shuffle(go.begin(),go.end(),rng);
for(int i=0;i<n;i++){
Add(go[i]);
if(i == 0 || Get() == 1) continue;
Rem(go[i]);
}
for(int i=0;i<n;i++) if(vis[go[i]]) Kill[go[i]] = 1;
D = tot;
if(D > n / 2) return 1;
if(D == 1) return n;
int ans = 1, l = 2 , r = n / D;
while(l <= r){
shuffle(go.begin(),go.end(),rng);
int B = (l + r) / 2;
for(int i=0;i<n;i++) if(!Kill[go[i]]) Rem(go[i]);
vector<int> to_kill;
for(int i = 0 ; i < n ; i++){
if(vis[go[i]] || Kill[go[i]]) continue;
if(tot == B * D){
to_kill.push_back(go[i]);
continue;
}
Add(go[i]);
if(tot > B && Get() > B){
Rem(go[i]);
to_kill.push_back(go[i]);
}
}
if(tot == B * D){
l = B + 1;
ans = B;
r = min(r, B + (int) to_kill.size() / D);
if(to_kill.size() < D) return ans;
for(int i=0;i<n;i++) if(vis[go[i]]) Kill[go[i]] = 1;
}
else{
for(int x : to_kill) Kill[x] = 1;
r = min(tot / D, B - 1);
}
}
return ans;
}
