#include "insects.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<long double, long double>
#define pld pair<ld, ld>
#define NEK 200000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001
using namespace std;
/*
vec<int> original_pole;
set<int> masina;
void move_inside(int x) {
masina.insert(x);
return;
}
void move_outside(int x) {
masina.erase(x);
return;
}
int press_button() {
unordered_map<int, int> umap;
int maxi = 0;
for (auto i : masina) {
umap[original_pole[i]]++;
maxi = max(maxi, umap[original_pole[i]]);
}
return maxi;
}*/
int dfs(int x, vec<int>& bol, vec<vec<int>>&g) {
bol[x] = 1;
int poc = 1;
for (auto i : g[x]) {
if (bol[i]) continue;
poc += dfs(i, bol, g);
}
return poc;
}
void vyries(vec<int>& v, vec<int>& o, vec<vec<int>>& g) {
if (v.size() == 0) return;
if (v.size() == 1) {
For(i, o.size()) {
g[o[i]].push_back(v[0]);
g[v[0]].push_back(o[i]);
}
move_outside(v[0]);
return;
}
int l = 0;
int r = v.size() - 1;
int mid = (l + r) / 2;
vec<int> v1, v2;
For(i, mid + 1) {
v1.push_back(v[i]);
}
for (int i = mid + 1; i < v.size(); i++) {
v2.push_back(v[i]);
move_outside(v[i]);
}
vec<int> o1, o2;
for (int i = 0; i < o.size(); i++) {
move_inside(o[i]);
int x = press_button();
move_outside(o[i]);
if (x == 1) {
o2.push_back(o[i]);
}
else {
o1.push_back(o[i]);
}
}
vyries(v1, o1, g);
for (int i = mid + 1; i < v.size(); i++) {
move_inside(v[i]);
}
vyries(v2, o2, g);
return;
}
int min_cardinality(int n) {
vec<vec<int>> g(n);
vec<int> v;
vec<int> o;
For(i, n) {
move_inside(i);
int x = press_button();
if (x == 1) {
v.push_back(i);
}
else {
o.push_back(i);
move_outside(i);
}
}
vyries(v, o, g);
vec<int> bol(n, 0);
int mini = n;
For(i, n) {
if (bol[i]) continue;
mini = min(mini, dfs(i, bol, g));
}
return mini;
}
/*
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n; cin >> n;
vec<int> p(n);
For(i, n) cin >> p[i];
original_pole = p;
cout << min_cardinality(n) << '\n';
return 0;
}
*/
