#include <bits/stdc++.h>
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
bool vis[2222];
int min_cardinality(int n){
int ans = 0;
for(int i=0;i<n;i++){
move_inside(i);
int r = press_button();
if(r > ans) ans = r, vis[i] = 1;
else move_outside(i);
}
for(int i=0;i<n;i++){
if(vis[i]) move_outside(i);
}
int lo = 1, hi = ans-1;
while(lo <= hi){
int mid = (lo+hi)/2;
int cnt = 0;
for(int i=0;i<n;i++){
if(vis[i]) move_inside(i), cnt++;
if(cnt == mid) break;
}
for(int i=0;i<n;i++){
if(!vis[i]) move_inside(i);
}
int r = press_button();
if(r == mid) ans = mid, hi = mid-1;
else lo = mid+1;
for(int i=0;i<n;i++){
if(vis[i]) move_outside(i), cnt--;
if(cnt == 0) break;
}
for(int i=0;i<n;i++){
if(!vis[i]) move_outside(i);
}
}
return ans;
}
