#include "insects.h"
#include "bits/stdc++.h"
using namespace std;
vector<int> v;
int D;
inline void Add(int x){
v.push_back(x);
move_inside(x);
}
inline void Rem(int x){
v.pop_back();
move_outside(x);
}
inline void Clear(){
while(!v.empty()){
move_outside(v.back());
v.pop_back();
}
}
inline int Get(){
return press_button();
}
int min_cardinality(int n){
for(int i=0;i<n;i++){
Add(i);
if(Get() == 1) continue;
Rem(i);
}
D = v.size();
if(D > n / 2) return 1;
if(D == 1) return n;
if(D <= 45){
vector<int> lead,vis(n,0),freq(D,1),L(n,0),R(n,D-1);
for(int x:v){
vis[x]=1;
lead.push_back(x);
}
for(int Q=0;Q<6;Q++){
vector<int> ask[n];
for(int i=0;i<n;i++){
if(L[i] == R[i] || vis[i]) continue;
int mid = (L[i]+R[i])/2;
ask[mid].push_back(i);
}
Clear();
for(int i=0;i<D;i++){
Add(lead[i]);
for(int x:ask[i]){
Add(x);
if(Get() == 2) R[x] = i;
else L[x] = i + 1;
Rem(x);
}
}
}
for(int i=0;i<n;i++){
if(vis[i]) continue;
freq[L[i]]++;
}
return *min_element(freq.begin(),freq.end());
}
int l = 1 , r = n / D;
while(l < r){
int B = (l + r + 1) / 2;
Clear();
for(int i=0;i<n;i++){
Add(i);
if(Get() > B){
Rem(i);
}
}
if(v.size() == B * D) l = B;
else r = B - 1;
}
return l;
}
