#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using ui = unsigned int;
using ull = unsigned long long;
using pui = pair<ui,ui>;
using pull = pair<ull,ull>;
template<typename T>
using vc = std::vector<T>;
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define yes cout << "yes\n"
#define no cout << "no\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
template<typename T> void sc(T &x) { cin >> x; }
template<typename T, typename U> void sc(pair<T,U> &p) { sc(p.first), sc(p.second); }
template<typename T> void sc(vector<T> &v) { for (auto &x : v) sc(x); }
template<typename... A> void sc(A&... a) { (sc(a), ...); }
template<typename T> void _pt(const T &x){cout << x;}
template<typename T, typename U> void _pt(const pair<T,U> &p){_pt(p.first); cout << ' '; _pt(p.second);}
template<typename T> void _pt(const vector<T> &v){bool f=1; for(auto &x:v){if(!f) cout<<' '; _pt(x); f=0;}}
template<typename... A> void pt(const A&... a){(_pt(a), ...);}
template<typename T, typename U> bool umin(T &a, const U &b) { return b < a ? (a = b, true) : false; }
template<typename T, typename U> bool umax(T &a, const U &b) { return b > a ? (a = b, true) : false; }
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define FOR1(n) for (int i=0; i<(n); ++i)
#define FOR2(i,n) for (int i=0; i<(n); ++i)
#define FOR3(i,l,r) for (int i=(l); i<(r); ++i)
#define FOR4(i,l,r,k) for (int i=(l); i<(r); i+=(k))
#define FOR(...) GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define ROF1(n) for (int i=(n)-1; i>=0; --i)
#define ROF2(i,n) for (int i=(n)-1; i>=0; --i)
#define ROF3(i,l,r) for (int i=(r)-1; i>=(l); --i)
#define ROF4(i,l,r,k) for (int i=(r)-1; i>=(l); i-=(k))
#define ROF(...) GET_MACRO(__VA_ARGS__, ROF4, ROF3, ROF2, ROF1)(__VA_ARGS__)
#define all(c) (c).begin(), (c).end()
#define allr(c) (c).rbegin(), (c).rend()
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define trav(x,a) for (auto &x : (a))
#define sz(a) ((int)(a).size())
#define mem(a,v) memset(a, v, sizeof(a))
#define nl pt("\n")
#include "mushrooms.h"
vi correct;
int used = 0;
// int use_machine(vi a) {
// used++;
// int n = sz(a);
// int ans = 0;
// FOR(n - 1) {
// if(correct[a[i]] != correct[a[i + 1]]) ans++;
// }
// return ans;
// }
// int lim = 125; // mozda se mora smanjiti
// int lim = 95;
int lim = 105;
int count_mushrooms(int n) {
int ans = 1;
set<int> nepoz;
FOR(i, 1, n)
nepoz.emplace(i);
vi a = {0}, b;
while(!nepoz.empty() && max(sz(a), sz(b)) < lim) {
if(sz(nepoz) == 1 || max(sz(a), sz(b)) == 1) {
int u = *nepoz.begin();
nepoz.erase(u);
int q = use_machine({0, u});
if(q)
b.pb(u);
else {
a.pb(u);
ans++;
}
}
else if(sz(nepoz) < 5 || max(sz(a), sz(b)) < 3 || min(sz(a), sz(b)) < 2) {
int u = *nepoz.begin(); nepoz.erase(u);
int v = *nepoz.begin(); nepoz.erase(v);
bool o = sz(a) < 2; // moze se desiti
int old = sz(a);
if(o) swap(a, b);
int q = use_machine({a[0], u, a[1], v});
if(!q) {
a.pb(u);
a.pb(v);
}
else if(q == 1) {
b.pb(v);
a.pb(u);
}
else if(q == 2) {
b.pb(u);
a.pb(v);
}
else {
b.pb(u);
b.pb(v);
}
if(o)
swap(a, b);
ans += sz(a) - old;
}
else {
int old = sz(a);
bool o = sz(a) < sz(b);
if(o) swap(a, b);
int u = *nepoz.begin(); nepoz.erase(u);
int v = *nepoz.begin(); nepoz.erase(v);
int w = *nepoz.begin(); nepoz.erase(w);
int q = use_machine({a[0], u, a[1], v, a[2], w});
if(q & 1) {
b.pb(w);
q--;
}
else {
a.pb(w);
}
if(!q) {
a.pb(u);
a.pb(v);
}
else if(q == 4) {
b.pb(u);
b.pb(v);
}
else {
int c = *nepoz.begin(); nepoz.erase(c);
int d = *nepoz.begin(); nepoz.erase(d);
q = use_machine({b[0], u, b[1], a[0], v, a[1], c, a[2], d}) - 1;
// max q = 7
if(q & 1) {
b.pb(d);
}
else {
a.pb(d);
}
if(q & 2) {
// odlucuje c za {q = 6 & q = 2 (q - 1)}
b.pb(c);
}
else {
a.pb(c);
}
if(q & 4) {
// odlucuje u i v {q = 4 & q = 6 (q - 1)};
b.pb(v);
a.pb(u);
}
else {
a.pb(v);
b.pb(u);
}
}
if(o) swap(a, b);
ans += sz(a) - old;
}
}
while(!nepoz.empty()) {
vi Q;
bool o = sz(a) < sz(b);
if(o) swap(a, b);
trav(x, a) {
Q.pb(x);
Q.pb(*nepoz.begin());
nepoz.erase(nepoz.begin());
if(nepoz.empty()) break;
}
int q = use_machine(Q);
if(q & 1) {
b.pb(Q.back());
}
else {
a.pb(Q.back());
}
if(o) swap(a, b);
ans += o ? ((q + 1) / 2) : ((sz(Q) / 2) - (q + 1) / 2);
}
return ans;
}
// int32_t main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int n;
// sc(n);
// correct.resize(n);
// sc(correct);
// int ans = count_mushrooms(n);
// // pt(ans); nl;
// // pt(count(all(correct), 0)); nl;
// pt(ans, "\nUsed:", used); nl;
// return 0;
// }
