#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
set<int> ls;
set<int> never;
int inside=1;
pair<set<int>, set<int>> putable(set<int>& available, int mk){
set<int> bigger;
set<int> smaller;
vector<int> te;
for(auto thing:available){
//cout << thing << ' ';
if(never.count(thing))continue;
move_inside(thing);
te.push_back(thing);
inside++;
if(press_button()>mk){
bigger.insert(thing);
move_outside(thing);
inside--;
}
else{
smaller.insert(thing);
}
}
for(auto thing:te){
available.erase(thing);
}
for(auto thing:bigger)available.insert(thing);
return {smaller, bigger};
}
int min_cardinality(int N) {
//dichotomie sur taille des grouppes max,c bien quand total tout est prenable,on "jette" les mauvais
int T=1;
vector<vector<int>> groups;
groups.push_back({0});
move_inside(0);
set<int> available;
for(int i = 1;i<N;i++){
move_inside(i);
inside++;
if(press_button()==2){
move_outside(i);
inside--;
available.insert(i);
}
else{
T++;
groups.push_back({i});
}
}
//cout << N << ' ' << T << '\n';
int res = 1;
int left = 1;
int right=(N)/T+1;
set<int> always;
while(left!=right){
//cout << left << ' ' << right << '\n';
//for(auto thing:available)cout << thing << ' ';
//cout << '\n';
int mid = left+(right-left)/2;
auto x = putable(available, mid);
//cout << inside << ' ' << mid << ' ' << T << '\n';
if(inside==(mid*T)){
//cout << inside << '\n';
//go higher
for(auto thing:x.second){
available.insert(thing);
}
left=mid+1;
for(int i = 0;i<N;i++)if(!available.count(i))always.insert(i);
}
else if (mid > left) {
for(auto thing:x.second)never.insert(thing);
for(auto thing:x.first){
if(!always.count(thing)){
move_outside(thing);
available.insert(thing);
inside--;
}
}
right=mid;
}
}
return left-1;
}
