#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> m;
vector<int> a, b, val;
/*
int use_machine(vector<int> &v){
int ret;
for (int x:v) printf("%d ", x);
printf("\n");
scanf("%d", &ret);
return ret;
}*/
int count_mushrooms(int n){
if (n<=226){
m.push_back(0);
int ret=1;
for (int i=1;i<n;i++){
m.push_back(i);
if (use_machine(m)==0) ret++;
m.pop_back();
}
//printf("%d\n", ret);
return ret;
}
m.push_back(0);
a.push_back(0);
for (int i=1;i<=2;i++){
m.push_back(i);
val.push_back(use_machine(m));
if (val.back()) b.push_back(i);
else a.push_back(i);
m.pop_back();
}
m.clear();
m.resize(4, 0);
int cur_state;
if (a.size()>b.size()){
cur_state=1;
m[1]=0; m[3]=a[1];
}
else{
cur_state=2;
m[1]=b[0]; m[3]=b[1];
}
int chk=3;
for (;(int)a.size()<142 && (int)b.size()<142;chk += 2){
m[0]=chk; m[2]=chk+1;
val.push_back(use_machine(m));
if (val.back()&1){
if (cur_state==1) b.push_back(chk);
else a.push_back(chk);
}
else{
if (cur_state==1) a.push_back(chk);
else b.push_back(chk);
}
if (val.back()&2){
if (cur_state==1) b.push_back(chk+1);
else a.push_back(chk+1);
}
else{
if (cur_state==1) a.push_back(chk+1);
else b.push_back(chk+1);
}
}
m.clear();
m.resize(284, 0);
if (a.size()>b.size()){
cur_state=1;
for (int i=0;i<142;i++) m[i*2+1]=a[i];
}
else{
cur_state=2;
for (int i=0;i<142;i++) m[i*2+1]=b[i];
}
int ans=0, ans2=(int)a.size();
int sz=max((int)a.size(), (int)b.size());
assert(sz==142 || sz==143);
while(true){
if (n-chk+1<=sz){
m.clear();
for (int i=0;i<sz;i++){
if (chk+i>=n){
break;
}
m.push_back(chk+i);
if (cur_state==1)m.push_back(a[i]);
else m.push_back(b[i]);
}
int tmp=use_machine(m);
tmp++;
if (cur_state==1) ans += ((int)m.size()/2-tmp/2);
else ans += tmp/2;
break;
}
m.clear();
m.resize(2*sz, 0);
for (int i=0;i<sz;i++){
if (cur_state==1) m[i*2+1]=a[i];
else m[i*2+1]=b[i];
}
for (int i=0;i<sz;i++){
m[i*2]=chk+i;
}
int tmp=use_machine(m);
tmp++;
if (cur_state==1) ans += (sz-tmp/2);
else ans += tmp/2;
/*if (tmp&1){
if (cur_state==1) b.push_back(m[0]);
else a.push_back(m[0]);
}
else{
if (cur_state==2) b.push_back(m[0]);
else a.push_back(m[0]);
}*/
chk += sz;
sz=max((int)a.size(), (int)b.size());
if (a.size()>b.size()) cur_state=1;
else cur_state=2;
}
//printf("%d\n", ans+(int)a.size());
return ans+ans2;
}
/*
int main(){
int n;
scanf("%d", &n);
count_mushrooms(n);
return 0;
}
*/
