using namespace std;
#include <bits/stdc++.h>
#include "mushrooms.h"
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<bool> vb;
typedef pair<int,int> pii;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
set<int> A, B;
int n;
int nextQuery = 1;
int ans = 1;
void qa() {
cerr << "a\n";
vi Q;
for (auto a : A) {
Q.pb(a);
Q.pb(nextQuery);
nextQuery++;
if (nextQuery == n) break;
}
int x = use_machine(Q);
int number_queried = Q.size() / 2;
int bs = x/2 + (x&1);
ans += number_queried - bs;
cerr << number_queried << " " << number_queried - bs << endl;
if (x & 1) B.insert(Q[Q.size() - 1]);
else A.insert(Q[Q.size() - 1]);
}
void qb() {
cerr << "b\n";
vi Q;
for (auto a : B) {
Q.pb(a);
Q.pb(nextQuery);
nextQuery++;
if (nextQuery == n) break;
}
int x = use_machine(Q);
int number_queried = Q.size() / 2;
int as = x/2 + (x&1);
ans += as;
cerr << number_queried << " " << as << endl;
if (x & 1) A.insert(Q[Q.size() - 1]);
else B.insert(Q[Q.size() - 1]);
}
void make_query() {
if (A.size() > B.size()) qa();
else qb();
}
void make_2_query() {
if (nextQuery >= n - 1) return;
vi Q;
int x1 = nextQuery;
int x2 = nextQuery+1;
nextQuery += 2;
if (A.size() > 2) {
auto ai = A.begin();
int a1 = *ai;
ai++;
int a2 = *ai;
Q = {a1, x1, a2, x2};
} else {
auto bi = B.begin();
int b1 = *bi;
bi++;
int b2 = *bi;
Q = {b1, x1, b2, x2};
}
int res = use_machine(Q);
if (A.size() < 2) res = 3 - res;
if (res == 0) {
A.insert(x1);
A.insert(x2);
ans+=2;
} else if (res == 1) {
A.insert(x1);
B.insert(x2);
ans++;
} else if (res == 2) {
B.insert(x1);
A.insert(x2);
ans++;
} else {
B.insert(x1);
B.insert(x2);
}
}
int count_mushrooms(int N) {
n = N;
A.insert(0);
rep(i,0,2) if (nextQuery != n) make_query();
int MAGIC_NUMBER = 10;
rep(i,0,MAGIC_NUMBER) {
make_2_query();
}
while (nextQuery != n) make_query();
return ans;
}
