#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
#define in move_inside
#define out move_outside
#define get press_button
signed min_cardinality(signed n) {
int num=0;
vector<int> v,rem;
rep(x,0,n){
in(x);
if (get()==2){
rem.pub(x);
out(x);
}
else{
v.pub(x);
num++;
}
}
for (auto it:v) out(it);
v.clear();
int ans=1;
while (true){
int best=1e9;
int h=-1;
rep(x,1,sz(rem)/num+1){
int temp=max(num*x-1,sz(rem)-num*x);
if (temp<best){
best=temp;
h=x;
}
}
if (h==-1) break;
vector<int> small,big;
for (auto it:rem){
in(it);
if (get()==h+1){
big.pub(it);
out(it);
}
else{
small.pub(it);
}
}
//cout<<sz(small)<<" "<<sz(big)<<endl;
if (sz(small)==h*num){
ans+=h;
rem=big;
}
else{
rem=small;
}
for (auto it:small) out(it);
}
return ans;
}
