#include <bits/stdc++.h>
using namespace std;
#include "insects.h"
//taken from https://dmoj.ca/src/4766178
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
#define pb push_back
#define fs first
#define sn second
#define ms(a, x) memset(a, x, sizeof(a))
#define SZ(v) ((int) (v).size())
#define ALL(v) (v).begin(), (v).end()
const int INF = 0x3f3f3f3f;
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << (x) << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << arr[_i]; cerr << endl;}
mt19937_64 rng(9438443753);
ll randInt(ll a, ll b){return uniform_int_distribution(a, b)(rng);}
const int CUT = 10;
int solveKillCol(vi vec){
if(vec.empty()) return INF;
shuffle(ALL(vec), rng);
vi newVec;
int sample = vec[0];
move_inside(sample);
for(int a : vec){
if(a == sample) continue;
move_inside(a);
if(press_button() == 1) newVec.pb(a);
move_outside(a);
}
return min(SZ(vec) - SZ(newVec), solveKillCol(newVec));
}
int solve(int n, int typeC, vi vec){
int lo = 1, hi = n/typeC;
while(lo < hi){
int mid = (lo+hi+1)/2;
vi inMach, outMach;
for(int a : vec){
move_inside(a);
int res = press_button();
if(res <= mid) inMach.pb(a);
else move_outside(a), outMach.pb(a);
}
if(SZ(inMach) == typeC*(mid-lo)){
lo = mid;
vec = outMach;
}
else {
hi = mid-1;
vec = inMach;
for(int a : inMach) move_outside(a);
}
}
return lo;
}
int min_cardinality(int n){
vi inMach, vec;
FR(i, n){
move_inside(i);
int res = press_button();
if(res == 2) move_outside(i), vec.pb(i);
else inMach.pb(i);
}
int typeC = SZ(inMach);
/*dbg(typeC);
dbgArr(inMach.begin(), SZ(inMach));
dbgArr(vec.begin(), SZ(vec));*/
if(false){
for(int a : inMach) move_outside(a), vec.pb(a);
return solveKillCol(vec);
}
else return solve(n, typeC, vec);
}
