#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> p2;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<p2> vp2;
#define rep(var,high) for(int var=0;var<high;var++)
#define repe(var,container) for(auto& var : container)
#define local 0
#if local
int N = 8;
map<int, int> insidemachine;
bool hasinit = false;
vi bois(N);
void init()
{
return;
if (hasinit) return;
hasinit = true;
//rep(i, N) bois[i] = rand() % N;
bois[0] = 1;
bois[1] = 1;
bois[2] = 1;
bois[3] = 2;
bois[4] = 2;
bois[5] = 2;
bois[6] = 2;
bois[7] = 2;
}
void move_inside(int i) { init(); insidemachine[bois[i]]++; }
void move_outside(int i) { if (insidemachine[bois[i]]) insidemachine[bois[i]]--; }
int press_button()
{
int ret = 0;
repe(el, insidemachine) ret = max(ret, el.second);
return ret;
}
int judgeans()
{
int ret = 100000000;
repe(el, insidemachine) if (el.second!=0) ret = min(ret, el.second);
return ret;
}
#else
void move_inside(int i);
void move_outside(int i);
int press_button();
#endif
int min_cardinality(int n)
{
int col = 0;
vi inside(n);
int types = 0;
rep(i, n)
{
move_inside(i);
inside[i] = true;
types++;
if (press_button() > 1)
{
move_outside(i);
inside[i] = false;
types--;
}
}
rep(i, n) if (inside[i]) move_outside(i);
if (types == 1) return n;
int high = n;
int low = 1;
vi isinside(n);
int insidemaballs = 0;
set<int> possible;
rep(i, n) possible.insert(i);
while (true)
{
int x = (high + low) / 2;
bool works = false;
if (n>=types*x)
{
repe(i, possible)
{
if (isinside[i]) continue;
move_inside(i);
isinside[i] = true;
insidemaballs++;
if (press_button() > x)
{
move_outside(i);
isinside[i] = false;
insidemaballs--;
}
if (insidemaballs>=types*x)
{
break;
}
}
if (insidemaballs == types * x) works = true;
if (works)
{
// Keep insects inside
}
if (!works)
{
rep(i, n)
{
if (!isinside[i])
{
possible.erase(i);
}
else
{
move_outside(i);
}
}
isinside = vi(n, false);
insidemaballs = 0;
}
}
// If they are all greater than or equal to ans, the answer is larger than x
if (works)
{
low = x;
}
else
{
high = x;
}
if (low+1==high)
{
return low;
}
}
//return colorcnt[0];
}
#if local
int main()
{
rep(i, 100000)
{
N = 2+rand() % 100;
//bois = { 2, 0, 0 ,0 ,2 ,0 ,0 };
//N = bois.size();
bois=vi(N);
rep(i, N) bois[i] = rand() % N;
insidemachine = map<int, int>();
rep(i, N) insidemachine[bois[i]]++;
int jans = 100000000;
repe(el, insidemachine) if (el.second != 0) jans = min(jans, el.second);
insidemachine = map<int, int>();
if (min_cardinality(N)!=jans)
{
cout << "ligma:; ";
rep(i, N)
{
cout << bois[i] << ", ";
}
cout << "\n\n";
__debugbreak();
}
}
}
#endif
