#include <bits/stdc++.h>
#ifndef LOCAL
#include "mushrooms.h"
#endif
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
return y > x ? (x = y, true) : false;
}
void debug_out() {
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
cerr << ' ' << A;
debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
for (int i = 0; i < n; ++i)
cerr << a[i] << ' ';
cerr << endl;
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
for (auto& e : v)
stream << e << ' ';
return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
return stream << p.first << ' ' << p.second;
}
int use_machine(vector<int> x);
int count_mushrooms_halfn(int n) {
if (n == 2) {
if (use_machine({0, 1}) == 1)
return 1;
return 2;
}
int ans = 1;
int x, y;
int i;
if (use_machine({0, 1}) == 0) {
x = 0;
y = 1;
i = 2;
++ans;
} else if (use_machine({0, 2}) == 0) {
x = 0;
y = 2;
i = 3;
++ans;
} else {
x = 1;
y = 2;
i = 3;
}
for (; i < n; i += 2) {
if (i == n - 1) {
ans += use_machine({0, i}) == 0;
break;
}
int res = use_machine({x, i, y, i + 1});
if (x == 0) {
if (res == 0)
ans += 2;
else if (res <= 2)
++ans;
} else {
if (res == 3)
ans += 2;
else if (res >= 1)
++ans;
}
}
return ans;
}
int CeilD(int x, int y) {
if (x % y)
return x / y + 1;
return x / y;
}
int count_mushrooms(int n) {
if (n <= 2) {
return 1 + (int)(use_machine({0, 1}) == 0);
}
const int maxS = 1e5;
int maxQ = n;
int asked = 0;
int askedSum = 0;
auto ask = [&](vector<int> x) {
// debug(x);
++asked;
askedSum += x.size();
assert(asked <= maxQ);
assert(askedSum <= maxS);
return use_machine(x);
};
int minVal = 1e9;
int minK = -1;
for (int k = 1; k <= n; ++k) {
if (2 * k >= n) break;
if (chkmin(minVal, k + CeilD(n, k))) {
minK = k;
}
}
int k = minK;
// debug(k);
vector<int> col(n, -1);
col[0] = 0;
vector<int> h[2];
h[0].push_back(0);
for (int i = 1; i <= 2; ++i) {
col[i] = ask({0, i});
h[col[i]].push_back(i);
}
int i = 3;
if (h[0].size() >= 2) {
while (true) {
if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
int res = ask({h[0][0], i, h[0][1], i + 1});
if (res == 0) {
col[i] = col[i + 1] = 0;
} else if (res == 1) {
col[i] = 0;
col[i + 1] = 1;
} else if (res == 2) {
col[i] = 1;
col[i + 1] = 0;
} else {
col[i] = col[i + 1] = 1;
}
h[col[i]].push_back(i);
h[col[i + 1]].push_back(i + 1);
i += 2;
}
} else {
while (true) {
if (h[0].size() >= k + 1 || h[1].size() >= k + 1) break;
int res = ask({h[1][0], i, h[1][1], i + 1});
if (res == 3) {
col[i] = col[i + 1] = 0;
} else if (res == 2) {
col[i] = 0;
col[i + 1] = 1;
} else if (res == 1) {
col[i] = 1;
col[i + 1] = 0;
} else {
col[i] = col[i + 1] = 1;
}
h[col[i]].push_back(i);
h[col[i + 1]].push_back(i + 1);
i += 2;
}
}
int ans = h[0].size();
if (h[0].size() >= h[1].size()) {
int k = h[0].size() - 1;
for (; i < n; i += k) {
int m = min(n, i + k) - i;
vector<int> x = {h[0][0]};
for (int j = 0; j < m; ++j) {
x.push_back(i + j);
x.push_back(h[0][j + 1]);
}
ans += m - ask(x) / 2;
}
} else {
int k = h[1].size() - 1;
for (; i < n; i += k) {
int m = min(n, i + k) - i;
vector<int> x = {h[1][0]};
for (int j = 0; j < m; ++j) {
x.push_back(i + j);
x.push_back(h[1][j + 1]);
}
ans += ask(x) / 2;
}
}
return ans;
}
#ifdef LOCAL
static char fmt_buffer[100000];
#define FMT_TO_STR(fmt, result) va_list vargs; va_start(vargs, fmt); \
vsnprintf(fmt_buffer, sizeof(fmt_buffer), fmt, vargs); \
va_end(vargs); fmt_buffer[sizeof(fmt_buffer)-1] = 0; \
std::string result(fmt_buffer);
static const int min_n = 2;
static const int max_n = 20000;
static const int max_qc = 20000;
static const int max_qs = 100000;
static const int species_A = 0;
static const int species_B = 1;
static int n;
static std::vector<int> species;
static int qc, qs;
static inline void error_if(bool cond, std::string message) {
if (cond) {
printf("%s\n", message.c_str());
exit(0);
}
}
static inline void wrong_if(bool cond, std::string message) {
error_if(cond, "Wrong Answer: "+message);
}
int use_machine(std::vector<int> x) {
const int xs = x.size();
wrong_if(xs < 2, "Too small array for query.");
wrong_if(xs > n, "Too large array for query.");
qc++;
wrong_if(qc > max_qc, "Too many queries.");
qs += xs;
wrong_if(qs > max_qs, "Too many total array sizes as queries.");
for (int i = 0; i < xs; i++)
wrong_if(x[i] < 0 || n - 1 < x[i], "Invalid value in the query array.");
std::vector<bool> used(n, false);
for (int i = 0; i < xs; i++) {
wrong_if(used[x[i]], "Duplicate value in the query array.");
used[x[i]] = true;
}
int diffs = 0;
for (int i = 1; i < xs; i++)
diffs += int(species[x[i]] != species[x[i-1]]);
return diffs;
}
#ifdef __GNUC__
__attribute__ ((format(printf, 2, 3)))
#endif
static inline void check_input(bool cond, const char* message_fmt, ...) {
FMT_TO_STR(message_fmt, message);
error_if(!cond, "Invalid input: "+message);
}
int main() {
freopen("in", "r", stdin);
check_input(1 == scanf("%d", &n), "Could not read n.");
check_input(min_n <= n, "n must not be less than %d, but it is %d.", min_n, n);
check_input(n <= max_n, "n must not be greater than %d, but it is %d.", max_n, n);
species.resize(n);
for (int i = 0; i < n; i++) {
check_input(1 == scanf("%d", &species[i]), "Could not read species element [%d].", i);
check_input(species[i]==species_A || species[i] == species_B,
"Species elements must be %d or %d, but species element [%d] is %d.", species_A, species_B, i, species[i]);
}
check_input(species[0] == species_A, "Species element [%d] must be %d.", 0, species_A);
// Postponed closing standard input in order to allow interactive usage of the grader.
qc = 0;
qs = 0;
int answer = count_mushrooms(n);
printf("%d\n", answer);
fclose(stdout);
fclose(stdin);
return 0;
}
// int32_t main() {
// #ifdef LOCAL
// freopen("in", "r", stdin);
// #endif
// ios::sync_with_stdio(0);
// cin.tie(0);
// return 0;
// }
#endif
