#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rng(1557);
vector<int> P;
set<int> qst, cd;
int n, t;
bool ins(int x){
bool ret = qst.insert(x).second;
if (ret) move_inside(P[x-1]);
return ret;
}
bool del(int x){
if (qst.find(x)==qst.end()) return 0;
qst.erase(x);
move_outside(P[x-1]);
return 1;
}
void get_type(){
for (int i=1;i<=n;i++){
ins(i);
if (press_button()>1) del(i);
}
t = qst.size();
for (int i=1;i<=n;i++) if (qst.find(i)==qst.end()) cd.insert(i);
}
bool ok(int c){
if (cd.empty()){
return (int)qst.size() == t*c;
}
if (qst.find(*cd.begin())!=qst.end()){
for (auto &x:cd) del(x);
}
for (auto &x:cd){
ins(x);
if (press_button()>c) del(x);
if ((int)qst.size() == t*c) break;
}
bool ret = (int)qst.size() == t*c;
for (auto iter=cd.begin();iter!=cd.end();){
if ((qst.find(*iter)!=qst.end())==ret) iter = cd.erase(iter);
else iter++;
}
return ret;
}
int min_cardinality(int N) {
for (int i=0;i<N;i++) P.push_back(i);
shuffle(P.begin(), P.end(), rng);
n = N;
get_type();
if (t==1) return n;
int l = 2, r = N / t, ans = 1;
while(l<=r){
int m = (l+r)>>1;
if (ok(m)) l = m+1, ans = m;
else r = m-1;
}
return ans;
}
