#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<int> qst, cd;
int n, t;
bool ins(int x){
bool ret = qst.insert(x).second;
if (ret) move_inside(x-1);
return ret;
}
bool del(int x){
if (qst.find(x)==qst.end()) return 0;
qst.erase(x);
move_outside(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;
if (ret){
for (auto iter=cd.begin();iter!=cd.end();){
if (qst.find(*iter)!=qst.end()) iter = cd.erase(iter);
else iter++;
}
}
else{
for (auto iter=cd.begin();iter!=cd.end();){
if (qst.find(*iter)==qst.end()) iter = cd.erase(iter);
else iter++;
}
}
return ret;
}
int min_cardinality(int N) {
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 + (r-l > 5)) / 2;
if (ok(m)) l = m+1, ans = m;
else r = m-1;
}
return ans;
}
