#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
#define DEBUG 0
#if DEBUG
string actual;
int use_machine(vector<int> arr){
cout << "? ";
for(auto x : arr) cout << x << " ";
cout << endl;
int count = 0;
for(int i = 1; i< arr.size(); i++){
if(actual[arr[i]] != actual[arr[i-1]]) count++;
}
return count;
}
#endif
pair<int,int> alternate(vector<int>& arr, int& i, int n){
int loopto = min((int)arr.size(),n-i);
vector<int> qarr;
for(int j = 0; j < loopto; j++){
qarr.push_back(arr[j]);
qarr.push_back(i+j);
}
i += loopto;
return {use_machine(qarr),loopto};
}
int count_mushrooms(int n) {
vector<int> A = {0};
vector<int> B;
int count = 0;
int i = 1;
while(i != n){
if(A.size() < B.size()){
pair<int,int> ret = alternate(B,i,n);
if(ret.first&1) A.push_back(i-1);
else B.push_back(i-1);
count += ret.first/2;
}
else{
pair<int,int> ret = alternate(A,i,n);
if(ret.first&1) B.push_back(i-1);
else A.push_back(i-1);
count += ret.second - 1 - ret.first/2;
}
}
return count + A.size();
}
