#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
map<vector<int>,int> store;
vector<int> cur,real_;
void add(int i)
{
i--;
cur.push_back(i);
}
void rem(int i)
{
i--;
cur.pop_back();
}
void khatam()
{
cur.clear();
}
int ask()
{
if(store.find(cur)!=store.end())return store[cur];
for(auto&i:cur)
{
if(!binary_search(begin(real_),end(real_),i))
{
move_inside(i);
}
}
for(auto&j:real_)
{
if(!binary_search(begin(cur),end(cur),j))
{
move_outside(j);
}
}
real_=cur;
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/sz)+1;
while(s+1<e)
{
int mid=(s+e)/2;
khatam();
int sm=0;
// if(sz>=mid)
// {
// for(int i=0;i<sz;i++)
// add(heads[i]),sm++;
for(int j=1;j<=n;j++)
{
if(!binary_search(begin(heads),end(heads),j))
{
add(j);
if(ask()>mid)
{
rem(j);
}
else{
sm++;
}
}
else
{
add(j);
sm++;
}
}
// }
// else
// {
// 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))
// {
// break;
// }
// }
// }
// }
if(sm==((sz*mid)))
{
s=mid;
}
else{
e=mid;
}
}
return s;
}
