// Be name khoda //
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define debug(x) cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
const int mod = 1e9 + 9;
const int maxn5 = 1e5 + 10;
int dif, n, pw[maxn5], per[maxn5], hsh = 0;
bool mark[maxn5];
vector <int> av;
map <int, int> asked;
int c[3];
void fix(int &a){
if(a < 0)
a += mod;
if(a >= mod)
a -= mod;
}
void mmove_outside(int x){
x = per[x];
move_outside(x);
fix(hsh -= pw[x]);
c[0]++;
}
void mmove_inside(int x){
x = per[x];
move_inside(x);
fix(hsh += pw[x]);
c[1]++;
}
int ppress_button(){
if(asked.find(hsh) == asked.end())
asked[hsh] = press_button();
c[2]++;
return asked[hsh];
}
int find_all_same(int id){
mark[id] = true;
mmove_inside(id);
int cnt = 1;
for(int i = 0; i < n; i++) if(!mark[i]){
mmove_inside(i);
if(ppress_button() == 2){
mark[i] = true;
cnt++;
}
mmove_outside(i);
}
mmove_outside(id);
return cnt;
}
int count_dif(){
av.clear();
hsh = 0;
for(int i = 0; i < n; i++){
mmove_inside(i);
av.pb(i);
if(ppress_button() == 2){
mmove_outside(i);
av.pop_back();
}
}
for(auto u : av)
mmove_outside(u);
return av.size();
}
bool check(int x){
av.clear();
hsh = 0;
for(int i = 0; i < n; i++){
av.pb(i);
mmove_inside(i);
if(i + 1 > x && ppress_button() > x){
mmove_outside(i);
av.pop_back();
}
if(int(av.size()) == x * dif)
break;
if(int(av.size()) + n - i - 1 < x * dif)
break;
}
for(auto u : av)
mmove_outside(u);
return int(av.size()) == x * dif;
}
int min_cardinality(int N) {
n = N;
pw[0] = 1;
for(int i = 0; i < n; i++){
per[i] = i;
if(i)
pw[i] = pw[i - 1] * 7ll % mod;
}
shuffle(per, per + n, rng);
dif = count_dif();
if(dif == 1)
return n;
if(dif <= 8){
int mn = n;
for(int i = 0; i < n; i++) if(!mark[i]){
mn = min(mn, find_all_same(i));
if(mn == 1)
return 1;
}
return mn;
}
int lo = 1, hi = n / dif + 1;
while(hi - lo > 1){
int mid = (lo + hi) >> 1;
if(check(mid))
lo = mid;
else
hi = mid;
}
return lo;
}
