#define ONLINE_JUDGE
#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)
template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
mt19937 jdg(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + jdg() % (r - l + 1); }
vector <int> insects;
int min_cardinality(int n) {
insects.assign(n, 0); iota(ALL(insects), 0);
shuffle(ALL(insects), jdg);
int cnt = 0;
vector <int> remain;
REP(i, n) {
move_inside(insects[i]);
if(press_button() > 1) {
move_outside(insects[i]);
remain.push_back(insects[i]);
} else cnt++;
}
if(cnt == 1) return n;
if(cnt == 2) {
REP(i, n) move_inside(insects[i]);
return n - press_button();
}
int l = 2, r = n / cnt, last = 1, ans = 1;
while(r >= l) {
int mid = l + r >> 1;
vector <int> new_remain, removing;
int res = 0, id = 0;
for (auto &x : remain) {
++id;
move_inside(x);
if(press_button() > mid) {
move_outside(x);
new_remain.push_back(x);
} else res++, removing.push_back(x);
if(res == cnt * (mid - last)) {
FOR(i, id, (int) remain.size() - 1) new_remain.push_back(remain[i]);
break;
}
}
if(res == cnt * (mid - last)) {
ans = last = mid;
l = mid + 1;
swap(remain, new_remain);
} else {
r = mid - 1;
for (auto x : removing) move_outside(x);
swap(remain, removing);
}
}
return ans;
}
