#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;
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
move_outside(i);
}
// for(auto i:machine)
// move_outside(i),sm--;
// machine.clear();
int sz=sm,np=n;
while(1)
{
int mid=(np)/sz;
// cout<<"AT "<<np<<' '<<sz<<' '<<mid<<endl;
for(auto i:machine)
move_outside(i);
sm=0;
machine.clear();
for(int i=0;i<n and sm<(sz*mid);i++)
{
if(machine.find(i)==machine.end())
{
move_inside(i);
if(press_button()>mid)
{
move_outside(i);
}
else
{
sm++;
machine.insert(i);
}
}
}
if(sm==((sz*mid)))
{
return mid; // this is the answer
}
else{
np=sm;
}
}
return -1;
}
