#include "insects.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/* DEFINES */
#define S second
#define F first
#define ll long long
#define ull unsigned long long
#define ld long double
#define npos ULLONG_MAX
#define INF LLONG_MAX
#define vv(a) vector<a>
#define pp(a, b) pair<a, b>
#define pq(a) priority_queue<a>
#define qq(a) queue<a>
#define ss(a) set<a>
#define mm(a, b) map<a, b>
#define ump(a, b) unordered_map<a, b>
#define sync \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define elif else if
#define endl "\n"
#define allc(a) begin(a), end(a)
#define all(a) a, a + sizeof(a) / sizeof(a[0])
#define pb push_back
#define logi(a) __lg(a)
#define sqrt(a) sqrtl(a)
#define mpr make_pair
#define ins insert
using namespace std;
using namespace __gnu_pbds;
using namespace __cxx11;
typedef char chr;
typedef basic_string<chr> str;
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int min_cardinality(int n)
{
if (n == 1)
return 1;
vv(ll) eq, uni;
for (ll i = 0; i < n; i++)
{
move_inside(i);
if (press_button() == 2)
eq.pb(i), move_outside(i);
else
uni.pb(i);
}
ll l = 1, cntdiff = n - eq.size(), r = n / cntdiff, d = cntdiff, cur = cntdiff;
if (cntdiff == 1)
return n;
if (cntdiff > (n >> 1))
return 1;
if (cntdiff <= 2)
{
vv(pp(ll, ll)) v;
ll a, b;
bool flg = 0;
for (ll i = 0; i < n; i++)
{
move_inside(i);
ll j;
for (j = 0; j < v.size(); j++)
{
a = v[j].S;
move_inside(a);
b = press_button();
move_outside(a);
if (b == 2)
{
v[j].F++;
break;
}
}
if (j == v.size())
v.pb(mpr(1, i));
move_outside(i);
}
return min_element(allc(v))->F;
}
bool us[n];
memset(us, 0, sizeof(us));
while (l <= r)
{
ll mid = (l + r) >> 1;
vv(ll) erase, tmp;
for (ll i : eq)
{
if (us[i])
continue;
us[i] = 1;
move_inside(i);
if (press_button() > mid)
move_outside(i), tmp.pb(i);
else
cur++, erase.pb(i);
if (cur >= mid * cntdiff)
{
l = mid + 1;
break;
}
}
if (cur >= mid * cntdiff)
{
l = mid + 1;
for (ll j : tmp)
us[j] = 0;
}
else
{
r = mid - 1;
cur -= erase.size();
for (ll i : erase)
move_outside(i), us[i] = 0;
}
}
return --l;
}
