#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int n)
{
set<int> machine,rem;
int sm=1;
machine.insert(0);
move_inside(0);
for(int i=1;i<n;i++)
{
move_inside(i);
if(press_button()==1)
{
sm++;
machine.insert(i);
}
else
{
rem.insert(i);
move_outside(i);
}
}
int sz=sm;
int s=1;
int e=(n/sz)+1;
while(s+1<e)
{
int mid=(s+e)/2;
vector<int> cur;
for(auto i:rem)
{
move_inside(i);
if(press_button()>mid)
{
move_outside(i);
}
else
{
sm++;
cur.push_back(i);
machine.insert(i);
if(sm==(sz*mid))
break;
}
}
if(sm==((sz*mid)))
{
s=mid;
// We can make values in amachin so keep
for(auto i:cur)
rem.erase(i);
}
else{
e=mid;
sm=0;
rem.clear();
for(auto i:machine)
{
rem.insert(i);
move_outside(i);
}
machine.clear();
}
}
return s;
}
