#include "insects.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf ((id<<1))
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 3e5+10;
const ll MOD = 1e9+2022;
ll sum(ll a, ll b){ return (a+b)%MOD;}
void chsum(ll &a, ll b){ a = (a+b)%MOD;}
ll mul(ll a, ll b){ return (a*b)%MOD; }
void chmul(ll &a, ll b){ a = (a*b)%MOD;}
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
int n, ANS;
vector<int>vec;
int min_cardinality(int N) {
n = N; ANS = n;
for(int i=0; i<n; i++){
move_inside(i); vec.pb(i);
}
while(vec.size()){
int val = press_button();
chmn(ANS, val);
int awal = vec.size(), same = 1; // awal segini
// for(auto in : vec) cout << in << ' ';
// cout << " awal\n";
// cout << val << " val\n";
while(true){
int l = 0, r=vec.size()-1, mid = 0, cnt = -1;
int pos = 0;
while(l<=r){
mid = md; // di dalem mid+1 - vec.size()-1
while(pos < mid+1){
move_outside(vec[pos]); pos++;
}
while(pos > mid+1){
pos--; move_inside(vec[pos]);
}
if((vec.empty() ? 0 : press_button()) != val) r = mid-1;
// yg mau dikeluarin kena
else l = mid+1, cnt = mid;
}
while(pos > 0){
pos--; move_inside(vec[pos]);
}
move_outside(vec[cnt+1]); // yg dikeluarin = max cardinality
vector<int>vec2;
for(int i=0; i<vec.size(); i++){
if(i == cnt+1) continue;
vec2.pb(vec[i]);
}
swap(vec, vec2);
// for(auto in : vec )cout << in << ' ';
// cout << " newvec\n";
if(press_button() == val) same++;
else break;
}
if(val*same == awal) break; // card udh sama semua
}
return ANS;
}
