#include "mushrooms.h"
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
int p[20010];
int query(vector<int> vc){
vector<int> ask=vc;
for(auto &x:ask){
x=p[x];
}
return use_machine(vc);
}
int count_mushrooms(int n) {
for(int i=0;i<n;i++)p[i]=i;
random_shuffle(&p[1],&p[n]);
vector<int> a={0},b;
if(n<=226){
int ans=1;
for(int i=1;i<n;i++){
if(query({0,i})==0)ans++;
}
return ans;
}
int cnt=1;
// if(query({0,cnt})==0){
// a.push_back(cnt);
// }else{
// b.push_back(cnt);
// }
// cnt++;
// if(query({0,cnt})==0){
// a.push_back(cnt);
// }else{
// b.push_back(cnt);
// }
// cnt++;
// int T=70;
// if(a.size()>b.size()){
// for(int i=0;i<T;i++){
// int u=query({cnt,a[0],cnt+1,a[1]});
// if(u&1){
// b.push_back(cnt);
// }else{
// a.push_back(cnt);
// }
// if(u&2){
// b.push_back(cnt+1);
// }else{
// a.push_back(cnt+1);
// }
// cnt+=2;
// }
// }else{
// for(int i=0;i<T;i++){
// int u=query({cnt,b[0],cnt+1,b[1]});
// if(u&1){
// a.push_back(cnt);
// }else{
// b.push_back(cnt);
// }
// if(u&2){
// a.push_back(cnt+1);
// }else{
// b.push_back(cnt+1);
// }
// cnt+=2;
// }
// }
int mx=200;
int ans=a.size();
while(cnt<n){
vector<int> q;
int xd=0,st=cnt;
if(a.size()>=b.size()){
int need=0;
if(a.size()<mx){
if(a.size()>=3)need=1;
for(int i=0;i<min((int)a.size(),3);i++){
if(cnt<n){
xd++;
q.push_back(cnt);
cnt++;
}
q.push_back(a[i]);
}
}else{
for(int i=0;i<a.size();i++){
if(cnt<n){
xd++;
q.push_back(cnt);
cnt++;
}
q.push_back(a[i]);
}
}
int ct=query(q);
if(ct%2==0){
a.push_back(st);
}else{
b.push_back(st);
}
int bs=(ct+1)/2;
int ok=0;
if(ct/2==xd-1){
ok=1;
for(int i=st+1;i<st+xd;i++){
b.push_back(i);
}
}
if(ct/2==0){
ok=1;
for(int i=st+1;i<st+xd;i++){
a.push_back(i);
}
}
if(ok==0&&need==1){
if(query({0,st+1})==1){
b.push_back(st+1);
a.push_back(st+2);
}else{
a.push_back(st+1);
b.push_back(st+2);
}
}
ans+=xd-bs;
}else{
int need=0;
if(b.size()<mx){
if(b.size()>=3)need=1;
for(int i=0;i<min((int)b.size(),3);i++){
if(cnt<n){
xd++;
q.push_back(cnt);
cnt++;
}
q.push_back(b[i]);
}
}else{
for(int i=0;i<b.size();i++){
if(cnt<n){
xd++;
q.push_back(cnt);
cnt++;
}
q.push_back(b[i]);
}
}
int ct=query(q);
if(ct%2==0){
b.push_back(st);
}else{
a.push_back(st);
}
int as=(ct+1)/2;
int ok=0;
if(ct/2==xd-1){
ok=1;
for(int i=st+1;i<st+xd;i++){
a.push_back(i);
}
}
if(ct/2==0){
ok=1;
for(int i=st+1;i<st+xd;i++){
b.push_back(i);
}
}
if(ok==0&&need==1){
if(query({0,st+1})==1){
b.push_back(st+1);
a.push_back(st+2);
}else{
a.push_back(st+1);
b.push_back(st+2);
}
}
ans+=as;
}
}
return ans;
}
