#include "insects.h"

#include <vector>
// #include <cstdio>

constexpr int MN=2010;

int solve(const std::vector<int> &v1,const std::vector<int> &v2){
  // printf("solving\n");
  // for(int i:v1) printf("%d ",i);printf("\n");
  // for(int i:v2) printf("%d ",i);printf("\n");
  int k=v1.size(),n=v2.size();
  if(n<k) return 0;
  int b=(n-1)/(2*k)+1;
  std::vector<int> in,ot;
  for(int v:v2){
    move_inside(v);
    if(press_button()>b+1){
      move_inside(v);
      ot.push_back(v);
    }else{
      in.push_back(v);
    }
  }
  for(int v:in) move_outside(v);
  int l=in.size();
  if(l==k*b){
    return b+solve(v1,ot);
  }else{
    return solve(v1,in);
  }
}

int min_cardinality(int N) {
  std::vector<int> vals,ids;
  for(int i=0;i<N;++i){
    move_inside(i);
    if(press_button()<=1){
      vals.push_back(i);
    }else{
      move_outside(i);
      ids.push_back(i);
    }
  }
  return solve(vals,ids)+1;
}