#include "insects.h"

#include <vector>
using std::vector;

#define push move_inside
#define pop move_outside
#define get press_button

// us -> vs, ws
vector<int> us, vs, ws;
void go(int thr) {
  vs.clear();
  ws.clear();
  for (const int u : us) {
    push(u);
    if (get() <= thr) {
      vs.push_back(u);
    } else {
      pop(u);
      ws.push_back(u);
    }
  }
}

int min_cardinality(int N) {
  us.resize(N);
  for (int u = 0; u < N; ++u) us[u] = u;
  
  int lo = 1;
  go(lo);
  const int K = vs.size();
  us.swap(ws);
  
  int hi = N / K;
  go(hi);
  if ((int)vs.size() >= K * (hi - lo)) {
    return hi;
  }
  for (const int v : vs) pop(v);
  us.swap(vs);
  
  // keep inside: lo insects of each type
  for (; lo + 1 < hi; ) {
    const int mid = (lo + hi) / 2;
    go(mid);
    if ((int)vs.size() >= K * (mid - lo)) {
      lo = mid;
      us.swap(ws);
    } else {
      hi = mid;
      for (const int v : vs) pop(v);
      us.swap(vs);
    }
  }
  return lo;
}