#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
//int cnt = 0;
#include "mushrooms.h"
//vector<int> B;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//int use_machine(vector<int> X) {
// cnt++;
// int res = 0;
// for (int i = 1; i < X.size(); i++) {
// if (B[X[i] - 1] != B[X[i - 1] - 1]) {
// res++;
// }
// }
// return res;
//}
int count_mushrooms(int n) {
vector<int> A(n);
for (int i = 0; i < n; i++) {
A[i] = i;
}
shuffle(A.begin() + 1, A.end(), rng);
int ans = 1;
int fir, sec;
int cur = use_machine({A[0], A[1]});
if (n == 2)
return ans + !cur;
int cur2 = use_machine({A[0], A[2]});
if (!cur || !cur2) {
ans += 1 + (!cur & !cur2);
fir = A[0];
if (!cur) {
sec = A[1];
}
else {
sec = A[2];
}
for (int i = 3; i < n; i += 3) {
if (n - i == 1) {
int diff = use_machine({fir, A[i]});
ans += 1 - diff;
}
else if (n - i == 2) {
int diff = use_machine({A[i], fir, A[i + 1]});
ans += 2 - diff;
}
else {
int diff = use_machine({A[i + 1], fir, A[i], sec, A[i + 2]});
if (diff <= 1) {
ans += 3 - diff;
}
else if(diff >= 3) {
ans += 4 - diff;
}
else {
int diff2 = use_machine({fir, A[i]});
if (diff2) {
ans += 2;
}
else {
ans++;
}
}
}
}
}
else {
fir = A[1], sec = A[2];
for (int i = 3; i < n; i += 3) {
if (n - i == 1) {
int diff = use_machine({fir, A[i]});
ans += diff;
}
else if (n - i == 2) {
int diff = use_machine({A[i], fir, A[i + 1]});
ans += diff;
}
else {
int diff = use_machine({A[i], fir, A[i + 2], sec, A[i + 1]});
if (diff <= 1) {
ans += diff;
}
else if(diff >= 3) {
ans += diff - 1;
}
else {
int diff2 = use_machine({fir, A[i + 2]});
if (diff2) {
ans ++;
}
else {
ans += 2;
}
}
}
}
}
return ans;
}
//int main() {
// int n;
// cin >> n;
//
// B.clear();
// B.resize(n);
//
// for (int i = 0; i < n; i++) {
// B[i] = rng() % 2;
// }
//
// int res = count_mushrooms(n);
// cout << res << ' ' << cnt << ' ' << n / cnt;
//}
