#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
const int sq = 83;
vector<int> a,b;
int n;
int ask(vector<int> v){
return use_machine(v);
}
int base(){
int ret = 1 , pos = 1;
if(n%2 == 0){
pos = 2;
vector<int> f = {0,1};
ret += 1-ask(f);
}
for(int i = pos ; i < n ; i += 2){
vector<int> f = {i,0,i+1};
ret += 2-ask(f);
}
return ret;
}
void step1(){
a = {0};
vector<int> f = {0,1} , f2 = {0,2};
if(ask(f) == 0){
a.push_back(1);
}else{
b.push_back(1);
}
if(ask(f2) == 0){
a.push_back(2);
}else{
b.push_back(2);
}
}
void step2(){
if(a.size() >= 2){
for(int i = 3 ; i < 2*sq ; i += 2){
vector<int> f = {a[0],i,a[1],i+1};
int num = ask(f);
if(num == 0){
a.push_back(i),a.push_back(i+1);
}else if(num == 1){
a.push_back(i),b.push_back(i+1);
}else if(num == 2){
b.push_back(i),a.push_back(i+1);
}else{
b.push_back(i),b.push_back(i+1);
}
}
}else{
for(int i = 3 ; i < 2*sq ; i += 2){
vector<int> f = {b[0],i,b[1],i+1};
int num = ask(f);
if(num == 0){
b.push_back(i),b.push_back(i+1);
}else if(num == 1){
b.push_back(i),a.push_back(i+1);
}else if(num == 2){
a.push_back(i),b.push_back(i+1);
}else{
a.push_back(i),a.push_back(i+1);
}
}
}
}
int sv1(int pos){
int num = 0;
vector<int> f;
for(int i = 0 , j = pos ; i < a.size() && j < n ; i += 1 , j += 1){
f.push_back(a[i]),f.push_back(j),num += 1;
}
num -= 1;
int val = ask(f);
if(val%2 == 0){
a.push_back(f.back());
}else{
b.push_back(f.back());
}
return num-val/2;
}
int sv2(int pos){
int num = 0;
vector<int> f;
for(int i = 0 , j = pos ; i < b.size() && j < n ; i += 1 , j += 1){
f.push_back(b[i]),f.push_back(j),num += 1;
}
num -= 1;
int val = ask(f);
if(val%2 == 0){
b.push_back(f.back());
}else{
a.push_back(f.back());
}
return val/2;
}
int step3(){
int ret = 0 , pos = 2*sq+1;
while(pos < n){
if(a.size() > b.size()){
int nxt = pos+a.size();
ret += sv1(pos);
pos = nxt;
}else{
int nxt = pos+b.size();
ret += sv2(pos);
pos = nxt;
}
}
return ret;
}
int count_mushrooms(int N){
n = N;
if(n <= 400){
return base();
}
step1();
step2();
return step3()+a.size();
}
