#include <bits/stdc++.h>
using namespace std;
string s = string(1000, 'A');
int use_machine(vector<int> x);
int countA(int type, vector<int> known, vector<int> unk) {
int n = known.size(), m = unk.size();
assert(n >= m);
vector<int> query(2*m);
for (int i = 0; i < 2*m; i++) {
query[i] = i % 2 == 0
? unk[i/2]
: known[i/2];
}
int cnt_dif = use_machine(query);
if (cnt_dif % 2) cnt_dif++;
cnt_dif /= 2;
int cntA = type == 0 ? m - cnt_dif : cnt_dif;
return cntA;
}
const int L = 144;
int count_mushrooms(int n) {
vector<int> mush[2];
mush[0] = {0};
int i;
for (i = 1; i < n && mush[0].size() < L && mush[1].size() < L;) {
if (i <= n-2 && max(mush[0].size(), mush[1].size()) >= 2) {
int qtype = mush[0].size() < mush[1].size();
int x = mush[qtype][0], y = mush[qtype][1];
int r = use_machine({i, x, i+1, y});
int i_dif = r == 1 || r == 3;
int i1_dif = r == 2 || r == 3;
int i_type = i_dif ^ qtype;
int i1_type = i1_dif ^ qtype;
mush[i_type].push_back(i);
// cout << i_type << " " << s[i] - 'A' << "\n";
mush[i1_type].push_back(i+1);
i += 2;
} else {
int type = use_machine({0, i});
mush[type].push_back(i);
i ++;
}
}
int ans = mush[0].size();
int qtype = mush[0].size() < mush[1].size();
while (i < n) {
vector<int> unk;
for (int j = 0; j < L && i+j < n; j++)
unk.push_back(i+j);
ans += countA(qtype, mush[qtype], unk);
i += unk.size();
}
return ans;
}
// 0 1 2 3 4 5 6 7
// A B B A B A B B
// int use_machine(vector<int> x) {
// for (int m : x) cout << m << " "; cout << endl;
// int r; cin >> r; return r;
// int k = x.size(), res = 0;
// for (int i = 0; i < k-1; i++)
// res += s[x[i]] != s[x[i+1]];
// for (int i = 0; i < k; i++) cout << s[x[i]];
// cout << " " << res << endl;
// return res;
// }
//
// int main() {
// for (int i = 0; i < 1000; i++) {
// s[i] += rand() % 2;
// }
// s[0] = 'A';
// cout << count_mushrooms(1000) << "\n";
// cout << ranges::count(s, 'A') << "\n";
// const int n = 20'000;
// int dp[n+1];
// memset(dp, 0x3f, sizeof dp);
// dp[1] = 0;
// for (int i = 1; i <= n; i++) {
// int x = (i+1)/2, q = 0;
// for (int j = 0; x > 0; q++, x -= 1 << j++);
// for (int j = i+1; j <= i+q && j <= n; j++)
// dp[j] = min(dp[j], dp[i] + 1);
//// if(i<=100)cout<<i<<" "<<dp[i]<<"\n";
// }
//
// int ans = 10000;
// for (int x = 1; x <= 1000; x++) {
// int part1 = x;
// int rem = n - (2*x - 1);
// int part2 = (rem+x-1)/x;
// cout << x << " " << part1 << " " << part2 << "\n";
// ans = min(ans, part1 + part2);
// }
// cout << ans;
// }
