/**
* In the name of Allah
* We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "mushrooms.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
//#define int long long
const char nl = '\n';
//string s;
//int use_machine(vector<int> x) {
//int cnt = 0;
//for (int i = 1; i < sz(x); ++i)if (s[x[i]] != s[x[i-1]])cnt += 1;
//return cnt;
//}
int count_mushrooms(int n) {
int k = 20;
int res = 1, start = 0;
vector<int> a(1), b;
for (int i = 1; i <= min(n-1, 2); ++i) {
vector<int> x = {0, i};
int cnt = use_machine(x);
if (cnt == 0)a.push_back(i), res += 1;
else b.push_back(i);
}
vector<int> newa = a, newb = b;
if (n <= 3)return res;
bool ok2 = false;
if (sz(b) == 2)swap(a, b), ok2 = true;
if (n == 4) {
vector<int> x = {0, 3};
if (use_machine(x) == 0)return res+1;
else return res;
}
//for (auto i: newa)cout << i << " ";
//cout << nl;
int i = 3;
while (i <= n-2) {
vector<int> x = {i, a[0], i+1, a[1]};
int cnt = use_machine(x);
if (cnt == 1) {
if (ok2)newa.push_back(i), newb.push_back(i+1), res += 1;
else newb.push_back(i), newa.push_back(i+1), res+=1;
}
if (cnt == 2) {
if (ok2)newa.push_back(i+1), newb.push_back(i), res += 1;
else newb.push_back(i+1), newa.push_back(i), res += 1;
}
if (cnt == 3) {
if (ok2)newa.push_back(i+1), newa.push_back(i), res += 2;
else newb.push_back(i+1), newb.push_back(i);
}
if (cnt == 0) {
if (ok2)newb.push_back(i+1), newb.push_back(i);
else newa.push_back(i+1), newa.push_back(i), res += 2;
}
i += 2;
if (sz(newa) == k || sz(newb) == k)break;
}
if (i < n && sz(newa) < k && sz(newb) < k) {
vector<int> x = {0, i};
if (use_machine(x) == 0)newa.push_back(i), res += 1;
else newb.push_back(i);
i += 1;
}
//cout << i << nl;
a = newa, b = newb;
if (sz(a) < k && sz(b) < k)return res;
//bool ok = false;
//if (sz(b) == k)swap(a, b), ok = true;
//vector<int> a(1), b;
while (i < n) {
int mn = min(n-i, k);
vector<int> x;
if (sz(a) >= sz(b))
for (int j = 0; j < mn; ++j) {
x.push_back(j+i);
x.push_back(a[j]);
}
else
for (int j = 0; j < mn; ++j) {
x.push_back(j+i);
x.push_back(b[j]);
}
int cnt = use_machine(x);
if (sz(a) >= sz(b))res += mn-(cnt+1)/2;
else res += (cnt+1)/2;
int onki = k;
if (cnt&1) {
if (sz(a) >= sz(b))b.push_back(i);
else a.push_back(i);
k = max(sz(a), sz(b));
}
i += onki;
}
return res;
}
//int main() {
//cin >> s;
//cout << count_mushrooms(sz(s));
//}
