//#define LOCAL
#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> representant;
vector<int> chef;
void solve(vector<int> inconnus,int inf,int sup){
#ifdef LOCAL
cout<<inf<<' '<<sup<<endl;
for(int v:inconnus){
cout<<v<<' ';
}cout<<endl;
#endif
if(inf==sup){
//feuilles
for(int i:inconnus){
chef[i] = representant[inf];
}
return;
}else{
int mid=(inf+sup)/2;
for(int i=inf;i<=mid;i++)move_inside(representant[i]);
vector<int> listLeft,listRight;
for(int Inc:inconnus){
move_inside(Inc);
if(press_button()==2){
listLeft.pb(Inc);
}else{
listRight.pb(Inc);
}
move_outside(Inc);
}
for(int i=inf;i<=mid;i++)move_outside(representant[i]);
solve(listLeft,inf,mid);
solve(listRight,mid+1,sup);
}
}
int min_cardinality(int N) {
chef.resize(N);
vector<int> inconnus;
for(int i=0;i<N;i++){
move_inside(i);
if(press_button()>1){
move_outside(i);
inconnus.pb(i);
}else{
chef[i]=i;
representant.pb(i);
}
}
for(int i:representant){
move_outside(i);
}
solve(inconnus,0,representant.size()-1);
map<int,int> mem;
for(int i=0;i<N;i++){
mem[chef[i]]++;
}
int mini = N+1;
#ifdef LOCAL
for(int i=0;i<N;i++){
cout<<chef[i]<<' ';
}
cout<<endl;
#endif
for(int i=0;i<N;i++){
mini = min(mini,mem[chef[i]]);
}
return mini;
}
