#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
/*vi cur;
int use_machine(vi v) {
int ans = 0;
for (int i = 0; i<v.size()-1; ++i) if (cur[v[i]] != cur[v[i+1]]) ++ans;
return ans;
}*/
int queryOne(int ind) {
//return cur[ind];
return 1-use_machine(vi{0, ind});
}
int naive(int n) {
int ans = 0;
for (int i = 1; i<n; ++i) ans += queryOne(i);
return ans+1;
}
int count_mushrooms(int n) {
if (n < 5) return naive(n);
vi temp(3); temp[0] = 1;
for (int i = 1; i<3; ++i) temp[i] = queryOne(i);
int a, b;
bool As = (temp[1] + temp[2]);
As ? (a = 0, b = (temp[1] ? 1 : 2)) : (a = 1, b = 2);
vi trans = As ? (vi){2, 1, 1, 0} : (vi){0, 1, 1, 2};
int ans = 1 + temp[1] + temp[2];
for (int i = 3; i<n-1; i += 2) {
int val = use_machine((vi){i, a, i+1, b});
ans += trans[val];
}
if (n % 2 == 0) ans += queryOne(n-1);
return ans;
}
/*
int main() {
for (int _ = 0; _ < 1000; ++_) {
int n = 5 + rand() % 20;
vi v(n, 1); for (int i = 1; i<n; ++i) v[i] = rand() % 2;
cur = v;
int val = count_mushrooms(n);
int real = accumulate(v.begin(), v.end(), 0);
if (val != real) {
cout << "a";
count_mushrooms(n);
}
}
}*/
/*
8
0 0 1 1 0 1 0 0
0 1 1 0 1 0 1 1
*/
