void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N);
#include <iostream>
#include <vector>
#include <set>
#include <map>
int size;
int type;
bool markBS[2010];
std::set<int> ins;
int cnt=0;
bool bs(int lim){
for(int i=0;i<size;i++){
if(markBS[i])continue;
move_inside(i);
if(press_button()>lim){
move_outside(i);
}
else{
cnt+=1;
ins.insert(i);
}
if(cnt>=lim*type){
for(auto mu:ins){
markBS[mu]=true;
}
return true;
}
//std::cout <<cnt << '*';
}
for (int i=0; i<size; i++) if (ins.find(i)==ins.end()) markBS[i]=1;
std::vector<int> tmp;
for(auto mu:ins){
if (markBS[mu]) continue;
tmp.push_back(mu);
move_outside(mu);
cnt-=1;
}
for (auto x:tmp) ins.erase(x);
return false;
}
int pbv;
int minL(){
int count = 0;
for(int i=0;i<size;i++){
move_inside(i);
pbv = press_button();
if(pbv>1){
move_outside(i);
}
else{
count+=1;
markBS[i]=true;
cnt+=1;
}
}
return count;
}
int min_cardinality(int N) {
size=N;
type = minL();
if(type==1)return size;
int l=1,r=1+(size/type);
int bstUse = 0;
while(l<r){
bstUse+=1;
int mid = (l+r+1)/2;
if(bs(mid)){
l=mid;
}
else{
r=mid-1;
}
//std::cout << cnt << ' ' << l << ' ' << mid << ' ' << r << '\n';
}
//std::cout << bstUse <<"*\n";
return l;
}
