#include<bits/stdc++.h>
#ifndef LOCAL
#include<insects.h>
#endif
using namespace std;
#ifdef LOCAL
const int MAX = 2e3 + 5;
int N;
int press[MAX];
vector<int> ar;
bool in[MAX];
int cnt[MAX]; //for testcase, use value <= 2000
multiset<int> st;
void move_inside(int i){
++press[0];
if(press[0] > 40000){
cout << "Too much operations move_inside!\n";
exit(0);
}
if(in[i]) {
cout << "Already added!\n";
exit(0);
}
in[i] = true;
if(cnt[ar[i]]) st.erase(st.find(cnt[ar[i]]));
cnt[ar[i]] += 1;
st.insert(cnt[ar[i]]);
}
void move_outside(int i){
++press[1];
if(press[1] > 40000){
cout << "Too much operations move_outside!\n";
exit(0);
}
if(!in[i]){
cout << "Not added yet!\n";
exit(0);
}
in[i] = false;
if(cnt[ar[i]]) st.erase(st.find(cnt[ar[i]]));
cnt[ar[i]] -= 1;
st.insert(cnt[ar[i]]);
}
int press_button(){
++press[2];
if(press[2] > 40000){
cout << "Too much operations press_button!\n";
exit(0);
}
if(st.empty()){
cout << "No insects!\n";
assert(false);
}
return *prev(st.end());
}
#endif
int ceil_divide(int a, int b){
return (a + b - 1) / b;
}
int min_cardinality(int N){
vector<int> inside_insects, outside_insects;
for(int i = 0; i < N; ++i){
move_inside(i);
if(press_button() > 1){
outside_insects.push_back(i);
move_outside(i);
} else inside_insects.push_back(i);
}
if(outside_insects.empty()) return 1;
int distinct_colors = (int)inside_insects.size();
for(int i : inside_insects) move_outside(i);
vector<int> greedy_insects = outside_insects;
int ans = 1;
while((int)greedy_insects.size() >= distinct_colors){
int nInsects = (int)greedy_insects.size();
int mid = ceil_divide(ceil_divide(nInsects, distinct_colors), 2);
vector<int> good, bad;
for(int i = 0; i < nInsects; ++i){
move_inside(greedy_insects[i]);
if(press_button() > mid){
bad.push_back(greedy_insects[i]);
move_outside(greedy_insects[i]);
} else{
good.push_back(greedy_insects[i]);
}
}
if(mid * distinct_colors == (int)good.size()){
ans += mid;
greedy_insects = bad;
} else greedy_insects = good;
if((int)greedy_insects.size() >= distinct_colors) for(int i : good) move_outside(i);
}
return ans;
}
#ifdef LOCAL
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int N = 6;
ar = {5, 8, 9, 8, 9, 9};
cout << min_cardinality(N);
return 0;
}
#endif
