#include "insects.h"

#include <bits/stdc++.h>
using namespace std;

const int MX=2005;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int cnt[MX], L[MX], R[MX];

int min_cardinality(int N) {
        vector<bool> vis(N);

        vector<int> pos;
        for(int i=0;i<N;i++) {
                if(vis[i]) continue;
                move_inside(i);

                if(press_button()==2) {
                        move_outside(i);
                } else {
                        vis[i]=true;
                        pos.push_back(i);
                }
        }

        if(pos.size()>=256) {
                int p=pos.size(),res=1;
                while(true) {
                        for(auto x:pos) {
                                move_outside(x);
                        }
                        pos.clear();

                        for(int i=0;i<N;i++) {
                                if(vis[i]) continue;
                                move_inside(i);

                                if(press_button()==2) {
                                        move_outside(i);
                                } else {
                                        vis[i]=true;
                                        pos.push_back(i);
                                }
                        }

                        if(pos.size()!=p) break;
                        res++;
                }

                return res;
        } else {
                for(auto x:pos) {
                        move_outside(x);
                }

                for(int i=0;i<N;i++) {
                        L[i]=0;
                        R[i]=pos.size()-1;
                }

                for(int it=0;it<8;it++) {
                        vector<array<int,3>> seg;
                        for(int i=0;i<N;i++) {
                                if(vis[i]) continue;

                                int m=(L[i]+R[i])/2;
                                if(R[i]>L[i]) {
                                        seg.push_back({L[i],m,i});
                                }
                        }
                        sort(seg.begin(),seg.end());

                        for(int i=0;i<seg.size();i++) {
                                int j=i;
                                while(j+1<seg.size() && seg[j+1][0]==seg[j][0]) j++;

                                for(int k=seg[i][0];k<=seg[i][1];k++) {
                                        move_inside(pos[k]);
                                }

                                for(int k=i;k<=j;k++) {
                                        move_inside(seg[k][2]);
                                        if(press_button()==2) {
                                                R[seg[k][2]]=seg[k][1];
                                        } else {
                                                L[seg[k][2]]=seg[k][1]+1;
                                        }
                                        move_outside(seg[k][2]);
                                }

                                for(int k=seg[i][0];k<=seg[i][1];k++) {
                                        move_outside(pos[k]);
                                }

                                i=j;
                        }
                }

                for(int i=0;i<N;i++) {
                        cnt[L[i]]++;
                }

                int res=N;
                for(int i=0;i<pos.size();i++) {
                        res=min(res,cnt[i]);
                }

                return res+1;
        }       
}