#include "insects.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#ifdef DEBUG
auto& operator<<(auto& os, pair<auto, auto> &p) {
return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto& os, const auto &v) {
os<<"{";
for(auto it=begin(v);it!=end(v);++it) {
if(it != begin(v)) os<<", ";
os<<(*it);
}
return os<<"}";
}
void dbg_out(auto... x) {
((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif
int n;
vi perm;
vi added;
void in(int i) {
if(added[i]) return;
added[i] = true;
move_inside(perm[i]);
}
void out(int i) {
if(!added[i]) return;
added[i] = false;
move_outside(perm[i]);
}
int button() {
int res = press_button();
dbg(added, res);
return res;
}
vi get_k() {
vi res;
rep(i,0,n) {
in(i);
if(button() > 1)
out(i);
else res.push_back(i);
}
rep(i,0,n) out(i);
return res;
}
int k;
vector<bool> removed;
pair<bool, vi> check(int x) {
rep(i,0,n) {
if(removed[i]) continue;
in(i);
if(button() > x) out(i);
}
vi vals;
rep(i,0,n)
if(added[i]) vals.push_back(i);
rep(i,0,n) out(i);
return {sz(vals) == k*x, vals};
}
int t = 0;
bool solve(int v) {
auto [poss, vals] = check(v - t);
if(poss) {
for(auto x : vals)
removed[x] = true;
t = v;
}
else {
fill(all(removed), true);
for(auto x : vals)
removed[x] = false;
}
return poss;
}
int min_cardinality(int N) {
n = N;
perm.resize(n);
iota(all(perm), 0);
random_shuffle(all(perm));
added.assign(n, 0);
vi ind = get_k();
k = sz(ind);
removed.assign(n, 0);
for(auto i : ind)
removed[i] = true;
if(k*5 >= n) {
if(solve(4)) return 5;
if(solve(3)) return 4;
if(solve(2)) return 3;
if(solve(1)) return 2;
return 1;
}
dbg(ind);
int t = 0;
int b = 0, e = (n - 1) / k;
while(b < e) {
int mid = (b + e + 1) / 2;
if(solve(mid)) b = mid;
else e = mid - 1;
}
return b + 1;
}
