#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) {
vector<int> rem(n - 1);
iota(all(rem), 1);
const int maxQ = 1e5;
int asked = 0;
int askedSum = 0;
auto ask = [&](vector<int> x) {
// debug(x);
++asked;
askedSum += x.size();
assert(askedSum <= maxQ);
return use_machine(x);
};
int ans = 1;
int k = 0;
vector<int> zeroes = {0};
while (!rem.empty() && (!k || CeilD(rem.size(), k) > asked && askedSum + 2 * rem.size() + CeilD(rem.size(), k) < maxQ / 2)) {
if (ask({0, rem[0]}) == 0) {
++ans;
++k;
zeroes.push_back(rem[0]);
rem.erase(rem.begin());
continue;
}
int vl = 0;
int vr = rem.size();
while (vr - vl > 1) {
int vm = (vl + vr) >> 1;
vector<int> x(rem.begin(), rem.begin() + vm + 1);
x.insert(x.begin(), 0);
if (ask(x) == 1)
vl = vm;
else
vr = vm;
}
if (vl == rem.size() - 1) {
rem.clear();
break;
}
++ans;
++k;
zeroes.push_back(rem[vr]);
vector<int> new_rem(rem.begin() + vr + 1, rem.end());
swap(rem, new_rem);
}
while (!rem.empty()) {
int m = min(k, (int)rem.size());
vector<int> y;
for (int i = 0; i < m; ++i) {
y.push_back(rem.back());
rem.pop_back();
}
vector<int> x = {0};
for (int i = 0; i < m; ++i) {
x.push_back(y[i]);
x.push_back(zeroes[i + 1]);
}
ans += m - 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%d\n", answer, qc);
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
