#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
map<set<int>,int> store;
set<int> cur,real_;
void add(int i)
{
i--;
cur.insert(i);
}
void rem(int i)
{
i--;
if(cur.find(i)!=cur.end())
cur.erase(i);
}
void khatam()
{
cur.clear();
}
int ask()
{
if(store.find(cur)!=store.end())return store[cur];
for(auto i:cur)
{
if(real_.find(i)==real_.end())
{
real_.insert(i);
move_inside(i);
}
}
set<int> rem;
for(auto j:real_)
{
if(cur.find(j)==cur.end())
{
rem.insert(j);
move_outside(j);
}
}
for(auto i:rem)real_.erase(i);
store[cur]=press_button();
// cout<<"asking \n";
// cout<<"For: ";
// for(auto i:cur)
// {
// cout<<i<<' ';
// }
// cout<<endl;
// cout<<"Ans: "<<store[cur]<<endl;
return store[cur];
}
int min_cardinality(int n)
{
vector<int> heads={1};
add(1);
for(int i=2;i<=n;i++)
{
add(i);
if(ask()==1)
heads.push_back(i);
else
rem(i);
}
int sz=heads.size();
int s=1;
int e=n+1;
while(s+1<e)
{
int mid=(s+e)/2;
khatam();
int sm=0;
for(int i=1;i<=mid;i++)
add(i),sm++;
for(int j=mid+1;j<=n;j++)
{
add(j);
if(ask()>mid)
{
rem(j);
}
else{
sm++;
}
}
if(sm==((sz*mid)))
{
s=mid;
}
else{
e=mid;
}
}
return s;
}
