#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
typedef long long ll;
#define OPT ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount
#define print(v) for(int i = 0; i < v.size(); i++) cout << v[i] << " "; cout<<endl;
int min_cardinality(int n)
{
int sz = 0;
set<int> out;
for (int i = 0; i < n; i++)
{
move_inside(i);
int x = press_button();
if (x > 1)
{
move_outside(i);
out.insert(i);
}
else sz++;
}
if (sz == n) return 1;
else if (sz == 1) return n;
int best = 1;
int rn = sz;
int l = 1;
int r = n/sz;
while (l <= r)
{
int mid = (l + r) >> 1;
set<int> temp;
set<int> nout;
for (auto it = out.begin(); it != out.end(); it++)
{
int i = *it;
if (rn == mid * sz)
{ // fill out to next out (nout)
for (auto j = it; j != out.end(); j++) nout.insert(*j);
break;
}
move_inside(i);
int x = press_button();
if (x > mid)
{
nout.insert(i);
move_outside(i);
}
else
{
rn++;
temp.insert(i);
}
}
// if true, previous elements not needed
// current elements not needed ?? yes
// (*) extras not needed (nout) if min is already lower <- important
if (rn == mid * sz)
{
best = max(best, mid);
l = mid + 1;
out.swap(nout);
}
else
{
r = mid - 1;
rn -= (int)(temp.size());
for (int x : temp)
{
move_outside(x);
}
out.swap(temp); // (*) <-
}
}
return best;
}
