#include <bits/stdc++.h>
using namespace std;
vector<int> inside;
unordered_set<int> sett;
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N)
{
// number of different types
for (int i = 0; i < N; i++)
{
move_inside(i);
if (press_button() > 1)
{
move_outside(i);
sett.insert(i);
}
else
inside.push_back(i);
}
int l = 1;
int r = N / inside.size() + 2;
// binary search
while (l < r)
{
int m = l + (r - l + 1) / 2;
vector<int> w;
vector<int> outs;
for (int i : sett)
{
move_inside(i);
if (press_button() > m)
{
move_outside(i);
outs.push_back(i);
}
else
w.push_back(i);
}
if (w.size() == inside.size() * (m - l))
{
l = m;
for (int i : w)
sett.erase(i);
}
else
{
for (int i : outs)
sett.erase(i);
for (int i : w)
move_outside(i);
r = m - 1;
}
}
return l;
}
