#include "insects.h"
#include <vector>
#include <climits>
#include <iostream>
#include <algorithm>
//#include <algobase.h>
using namespace std;
#define ll long long 
#define ff first
#define ss second
#define pb push_back
int rep[10001];
int n ;
bool in[10001];
int cnt[10001];
bool past[10001];
vector<int>diff;
int total;
void joinn(int a, int b){
	if(!in[a])move_inside(a);
	if(!in[b])move_inside(b);
	int k = press_button();
	if(k == 2){
		rep[b] = a;
		cnt[a] ++ ;
		cnt[b] = INT_MAX;
		past[a] = true;
		past[b] = true;
	}
}
void findDiff(){
	diff.pb(0);
	move_inside(0);
	past[0] = true;
	cnt[0] = 1;
	for(int i = 1 ; i < n ; i ++){
		move_inside(i);
		int k = press_button();
		if(k == 1){
			diff.pb(i);
			past[i] = true;
			cnt [i] = 1;
		}else move_outside(i);
	}
	for(auto i : diff)move_outside(i);
	total = diff.size();
}
struct process{
	int l,r, pos;
	bool operator<(process otro){
		if(l < otro.l)return true;
		else if(l == otro.l and r < otro.r)return true;
		else return false;
	}
};
vector<process>queries;
vector<process>aux;
int curL = 0, curR = 0;
void add(int k){
	move_inside(diff[k]);
}
void quit(int k){
	move_outside(diff[k]);
}
void moveTo(int l, int r){
	while(curR < r){
		add(curR+1);
		curR ++ ;
	}

	while(curL > l){
		add(curL-1);
		curL --;
	}
	while(curR > r){
		quit(curR);
		curR--;
	}
	while(curL < l){
		quit(curL);
		curL ++ ;
	}
}
void pp(int q){
	if(queries[q].l == queries[q].r){
		rep[queries[q].pos] = diff[queries[q].l];
		cnt[diff[queries[q].l]] ++ ;
		cnt[queries[q].pos] = INT_MAX;
		//cout << queries[q].pos << "belongs to " << diff[queries[q].l] << endl;
		return ;
	}
	int mid = (queries[q].l + queries[q].r)/2;
	moveTo(queries[q].l, mid);
	move_inside(queries[q].pos);
	int k = press_button();
	if(k == 2){
		aux.pb({queries[q].l, mid, queries[q].pos});
		//cout << "buscando ahora en " << queries[q].l << " " << mid << " *" << queries[q].pos << endl;
	}else{
		aux.pb({mid+1, queries[q].r, queries[q].pos});
		//cout << "buscando ahora en " << mid+1 << " " << queries[q].r << " *" << queries[q].pos << endl;
	}
	move_outside(queries[q].pos);
}
int min_cardinality(int N) {
	
	n = N;
	for(int i = 0 ; i < N ; i ++){
		rep[i] = i;
		cnt[i] = 0;
		past[i] = false;
	}

	findDiff();
	//cout << "diff: " << endl;
	//for(auto i : diff) cout << i << " " ;
	//cout << endl;
	for(int i = 0 ; i < n ; i ++){
		if(!past[i])queries.pb({0, total-1, i});
	}
	add(0);
	while(!queries.empty()){
		int nn = queries.size();
		for(int i = 0 ; i < nn ; i ++){
			pp(i);	
		}
		sort(aux.begin(), aux.end());	
		queries = aux;
		aux.clear();
	}
	


	int mini = INT_MAX;
	for(int i = 0 ; i < n ; i ++){
		//cout << "i = " << i << " " << cnt[i] << "\n";
		mini = min(mini, cnt[i]);
	}
	return mini;
}