// In the name of Allah
#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define endl '\n'
#define sep ' '
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
const int maxn = 2000 + 4;
int n, k, sz, res;
set<int> st; vector<int> ls;
int M[maxn], Mx[maxn];
void addx(int j) {
st.insert(j); move_inside(j);
}
void delx(int j) {
st.erase(j); move_outside(j);
}
int askx() {
return press_button();
}
void del_all() {
while (!st.empty()) {
int j = *st.begin();
delx(j);
}
}
void cal_sz() {
sz = 0;
for (int i = 0; i < n; i++) {
if (!M[i]) sz++;
}
}
void checkx(ll R) {
del_all();
fill(Mx, Mx + n, 0); int cnt = 0;
for (int i = 0; i < n; i++) {
if (M[i]) continue;
addx(i);
if (askx() > R) delx(i);
else {
Mx[i] = 1; cnt++;
}
}
if (cnt == k * R) {
res += R;
for (int i = 0; i < n; i++) {
if (M[i]) continue;
if (Mx[i]) M[i] = 1;
}
}
else {
del_all();
for (int i = n - 1; i >= 0; i--) {
if (M[i]) continue;
if (!Mx[i]) {
M[i] = 1;
addx(i);
if (askx() > 1) delx(i);
}
}
k -= len(st);
for (int i = n - 1; i >= 0; i--) {
if (M[i]) continue;
addx(i);
if (askx() > 1) M[i] = 1;
delx(i);
}
}
cal_sz();
}
int min_cardinality(int N) {
n = N; sz = n;
for (int i = 0; i < n; i++) {
addx(i);
if (askx() > 1) delx(i);
}
for (int j : st) {
ls.pb(j); M[j] = 1;
}
k = len(ls);
res += 1; cal_sz();
while (sz >= k) {
int h = (sz / k);
checkx((h + 1) / 2);
}
return res;
}
