#include <bits/stdc++.h>
using namespace std;
namespace {
const int N = 139;
vector<int64_t> dp;
pair<vector<int>, int> unrank(int64_t x) {
int len = 0;
while (x >= dp[len]) {
x -= dp[len++];
}
int ans_len = len;
vector<int> ans;
while (len) {
int64_t num_emp = 1, num_2, num_3;
if (len <= 3) {
num_2 = len >= 2, num_3 = len >= 3;
} else {
num_2 = dp[len - 2], num_3 = dp[len - 3];
}
if (x >= num_emp + num_2) {
ans.push_back(3);
x -= num_emp + num_2, len -= 3;
} else if (x >= num_emp) {
ans.push_back(2);
x -= num_emp, len -= 2;
} else {
break;
}
}
reverse(ans.begin(), ans.end());
return {ans, ans_len};
}
} // namespace
int Declare() {
dp.resize(N + 1);
dp[0] = 1, dp[1] = 1, dp[2] = 2;
for (int i = 3; i <= N; ++i) {
dp[i] = dp[i - 2] + dp[i - 3] + 1;
}
return N + 1;
}
pair<vector<int>, vector<int>> Anna(long long A) {
int c = A & 1;
auto [seq, len] = unrank(A >> 1);
vector<int> a = {c};
/* rainboy: https://oj.uz/submission/651435 */
for (int &i : seq) {
if (i == 2) {
a.push_back(c), a.push_back(c);
} else {
c = !c;
a.push_back(c), a.push_back(c), a.push_back(c);
}
}
while (a.size() != len + 1) {
a.push_back(c = !c);
}
vector<int> b(a.size());
for (int i = 0; i < a.size(); i++) {
b[i] = (i + (A & 1)) & 1;
}
return {a, b};
}
#include <bits/stdc++.h>
using namespace std;
namespace {
const int N = 139;
vector<int64_t> dp;
int64_t rerank(vector<int> seq, int len) {
int64_t ans = 0;
for (int i = 0; i < len; ++i) {
ans += dp[i];
}
while (!seq.empty()) {
int64_t num_emp = 1, num_2, num_3;
if (len <= 3) {
num_2 = len >= 2, num_3 = len >= 3;
} else {
num_2 = dp[len - 2], num_3 = dp[len - 3];
}
if (seq.back() == 2) {
ans += num_emp, len -= 2;
} else {
ans += num_emp + num_2, len -= 3;
}
seq.pop_back();
}
return ans;
}
} // namespace
long long Bruno(vector<int> u) {
int c = u[0], cc = u[0];
if (c == 0) {
c = 1;
for (int &i : u) {
i = 1 - i;
}
}
dp.resize(N + 1);
dp[0] = 1, dp[1] = 1, dp[2] = 2;
for (int i = 3; i <= N; ++i) {
dp[i] = dp[i - 2] + dp[i - 3] + 1;
}
vector<int> seq;
int sum = 0;
for (int &i : u | views::drop(1)) {
sum += (i << 1) - 1;
if (c == 1 && sum >= 2) {
seq.push_back(2);
sum = 0;
}
if (c == 1 && sum <= -2) {
seq.push_back(3);
sum = 0, c = 0;
}
if (c == 0 && sum <= -2) {
seq.push_back(2);
sum = 0;
}
if (c == 0 && sum >= 2) {
seq.push_back(3);
sum = 0, c = 1;
}
}
return rerank(seq, u.size() / 2 - 1) << 1 | cc;
}
