/*************************************
* author: marvinthang *
* created: 25.08.2022 22:19:29 *
*************************************/
#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define fi first
#define se second
#define div ___div
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define FULL(i) (MASK(i) - 1)
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T> print_op(vector <T>) { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V> scan_op(pair <U, V>) { return in >> u.fi >> u.se; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.fi << ", " << u.se << ')'; }
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
set <int> insides;
void add(int i) {
move_inside(i);
insides.insert(i);
}
void remove(int i) {
move_outside(i);
insides.erase(i);
}
void reset_machine(void) {
set <int> tmp = insides;
for (int i: tmp) remove(i);
}
int min_cardinality(int n) {
for (int i = 0; i < n; ++i) {
add(i);
if (press_button() > 1) remove(i);
}
int unique_vals = insides.size();
reset_machine();
int l = 2, r = n / unique_vals;
while (l <= r) {
int m = l + r >> 1;
set <int> just_added;
for (int i = 0; i < n; ++i) {
add(i);
if (press_button() > m) remove(i);
else just_added.insert(i);
}
int total = insides.size();
reset_machine();
if (total >= unique_vals * m) l = m + 1;
else {
r = m - 1;
for (int i: just_added) remove(i);
}
}
return r;
}
