#include "insects.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define SN 2000
using namespace std;
int scnt,ans;
bool used[SN+1];
void solve(int l,int r,vector<int>p,int op)
{
    if (l==r)
    {
	ans=l;
	return;
    }
    vector<int>A;
    vector<int>B;
    int mid=(l+r)>>1,res,ps=0;
    if (op)
    {
	for (int j=0;j<op;++j) A.push_back(p[j]);
    }
    for (int i=op;i<p.size();++i)
    {
        move_inside(p[i]),res=press_button();
	if (res>mid-l+1) move_outside(p[i]),B.push_back(p[i]);
	else
	{
	    A.push_back(p[i]);
	    if (res<((mid-l+1)>>1)) ps=A.size();
	}
    }
    for (int i=(int)(A.size())-1;i>=ps;--i) move_outside(A[i]);
    if (A.size()<scnt*(mid-l+1)) solve(l,mid,A,ps);
    else move_outside(A[0]),solve(mid+1,r,B,0);
    return;
}
int min_cardinality(int N)
{
    vector<int>p;
    int res;
    for (int i=0;i<N;++i)
    {
	move_inside(i),res=press_button();
	if (res>1) move_outside(i),p.push_back(i);
	else scnt++,used[i]=1;
    }
    for (int i=0;i<N;++i)
	if (used[i])
	    move_outside(i);
    solve(1,N/scnt,p,0);
    return ans;
}