#include <iostream>
#include <vector>
#include <unordered_set>
#include <limits>
#include <set>
using namespace std;

void move_inside(int i);
void move_outside(int i);
int press_button();

set<int> get_representatives(int insect_count) {
    set<int> out;
    for (int i = 0; i < insect_count; ++i) {
        move_inside(i);
        if (press_button() == 1) {
            out.insert(i);
        } else {
            move_outside(i);
        }
    }

    for (int representative : out) {
        move_outside(representative);
    }
    return out;
}

int min_cardinality(int insect_count) {
    // press button, move inside, and move outside insect_count times
    set<int> representatives = get_representatives(insect_count);
   
    vector<unordered_set<int>> equivalence_tree;
    equivalence_tree.resize(2 * insect_count);

    // populate tree
    //      add non-representatives
    for (int i = 0; i < insect_count; ++i) {
        if (representatives.find(i) == representatives.end()) {
            equivalence_tree[1].insert(i);
        }
    }

    //      find child nodes
    for (int i = 2; i < equivalence_tree.size(); ++i) {
        unordered_set<int> &parent = equivalence_tree[i / 2];
       
        vector<int> cleanup_list;
        auto cursor = representatives.begin();
        for (int j = 0; j < representatives.size() / 2; ++j) {
            move_inside(*cursor);
            cleanup_list.push_back(*cursor);
            ++cursor;
        }
        for (int candidate : parent) {
            move_inside(candidate);
            if (press_button() == 2) {
                // candidate belongs to this node
                equivalence_tree[i].insert(candidate);
            }
            move_outside(candidate);
        }
        for (int litter : cleanup_list) {
            move_outside(litter);
        }
    }

    int minimum = numeric_limits<int>::max();
    for (int i = 1; i <= 4; ++i) {
        int cardinality = equivalence_tree[equivalence_tree.size() - i].size();
        if (cardinality < minimum) {
            minimum = cardinality;
        }
    }

    return minimum;
}