#include "insects.h"

#include <numeric>
#include <vector>

int min_cardinality(int n) {
    int beg = 0, end = n;
    while (beg + 1 < end) {
        int mid = (beg + end) / 2;
        std::vector<bool> fucked(n);
        std::vector<int> vec;

        for (int i = 0; i < n; i++) {
            move_inside(i);
            if (mid < press_button()) {
                fucked[i] = true;
                move_outside(i);
            } else {
                vec.push_back(i);
            }
        }
        for (int i : vec) {
            move_outside(i);
        }
        vec.clear();
        for (int i = n - 1; i >= 0; i--) {
            move_inside(i);
            if (mid < press_button()) {
                fucked[i] = true;
                move_outside(i);
            } else {
                vec.push_back(i);
            }
        }
        for (int i : vec) {
            move_outside(i);
        }
        vec.clear();

        if (std::accumulate(fucked.begin(), fucked.end(), 0) == n) {
            beg = mid;
        } else {
            end = mid;
        }
    }
    return end;
}