#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
int min_cardinality(int N) {
vector<int> a(N);
for (int i=0; i<N; ++i){
a[i] = i;
}
random_shuffle(a.begin(),a.end());
bitset<2000> inside;
int nbElems = 0;
for (int i=0; i<N; ++i){
move_inside(a[i]);
if (i != 0){
int maxFreq = press_button();
if (maxFreq > 1) move_outside(a[i]);
else{
++nbElems;
inside[a[i]] = true;
}
}
else{
++nbElems;
inside[a[i]] = true;
}
}
if (nbElems == 1) return N;
if (nbElems == N) return 1;
int in = nbElems, crt = 1;
int deb = 3, fin = N/nbElems, ans = 2;
vector<int> last;
while (deb <= fin){
int mid = (deb+fin)/2;
bool ok = false;
if (crt > mid){
for (int i=0; i<crt-mid; ++i){
inside[last.back()] = false;
move_outside(last.back());
last.pop_back();
in--;
}
while (!last.empty()){
if (press_button() == mid) break;
int l = last.back();
move_outside(l);
inside[l] = false;
last.pop_back();
in--;
}
if (last.empty()) return ans;
if (in == nbElems*mid) ok = true;
crt = mid;
}
last.clear();
int delta = mid-crt;
if (!ok){
for (int i=0; i<N; ++i){
if (!inside[a[i]]){
move_inside(a[i]);
--delta;
++in;
if (delta >= 0) continue;
if (in == mid*nbElems){
ok = true;
break;
}
crt = press_button();
if (crt > mid){
move_outside(a[i]);
--in;
--crt;
}
else{
inside[a[i]] = true;
last.emplace_back(a[i]);
}
}
}
}
if (ok){
crt = mid;
ans = mid;
deb = mid+1;
}
else fin = mid-1;
}
return ans;
/* for (int iter=0; iter<N; ++iter){
vector<int> idx;
for (int i=0; i<N; ++i){
if (!inside[a[i]]) idx.emplace_back(a[i]);
}
if (idx.empty()) return crt;
// random_shuffle(idx.begin(),idx.end());
for (int i=0; i<idx.size(); ++i){
move_inside(idx[i]);
if (press_button() == crt+1){
in++;
inside[idx[i]] = true;
}
else move_outside(idx[i]);
if (in%nbElems == 0) ++crt;
}
}*/
return crt;
}
