#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int same[2002], par[2002], cnt[2002];
vector<int> ind;
int query(vector<int> &vec){
static vector<int> recent (0);
sort(recent.begin(), recent.end());
sort(vec.begin(), vec.end());
for(int i=0, j=0; i<(int)recent.size() || j<(int)vec.size(); ){
if(i == (int)recent.size()) move_inside(vec[j++]-1);
else if(j == (int)vec.size()) move_outside(vec[i++]-1);
else if(recent[i] < vec[j]) move_outside(vec[i++]-1);
else if(recent[i] > vec[j]) move_inside(vec[j++]-1);
else i++, j++;
}
recent = vec;
return press_button();
}
int min_cardinality(int N){
n = N;
for(int i=1; i<=n; i++){
int l = 0, r = (int)ind.size()-1, key = (int)ind.size();
while(l <= r){
int m = (l+r)/2;
vector<int> v (1, i);
for(int j=0; j<=m; j++) v.push_back(ind[j]);
if(query(v) == 2) key = m, r = m-1;
else l = m+1;
}
if(key == (int)ind.size()) ind.push_back(i), par[i] = i, cnt[i] = 1;
else par[i] = ind[key], cnt[ind[key]]++;
}
int ans = n;
for(int i=1; i<=n; i++) if(cnt[i]) ans = min(ans, cnt[i]);
return ans;
}
