#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int ask(vi v)
{
if (SZ(v) <= 1) return 0;
return use_machine(v);
}
int N, ans;
vi as, bs;
int count_mushrooms(int n)
{
N = n;
// int MAGIC = 5;
int MAGIC = min(180, N - 1);
as.PB(0);
FOR(i, 1, MAGIC + 1)
{
vi v;
v.PB(0);
v.PB(i);
int q = ask(v);
if (q == 1)
{
//they're different
bs.PB(i);
}
else
{
as.PB(i);
}
}
ans = SZ(as);
if (SZ(bs) > SZ(as))
{
//we'll be counting how many bs there are in here.
int j = MAGIC + 1;
while(j < N)
{
vi tmp = bs, v;
v.PB(tmp.back());
tmp.pop_back();
while(j < N && !tmp.empty())
{
v.PB(j);
v.PB(tmp.back());
tmp.pop_back();
j++;
}
int c = ask(v);
ans += (c / 2);
}
}
else
{
int j = MAGIC + 1;
while(j < N)
{
vi tmp = as, v;
v.PB(tmp.back());
tmp.pop_back();
while(j < N && !tmp.empty())
{
v.PB(j);
v.PB(tmp.back());
tmp.pop_back();
j++;
ans++;
}
int c = ask(v);
ans -= (c / 2);
}
}
return ans;
// std::vector<int> m;
// for (int i = 0; i < n; i++)
// m.push_back(i);
// int c1 = use_machine(m);
// m = {0, 1};
// int c2 = use_machine(m);
// return c1+c2;
}
