#include <bits/stdc++.h>
using namespace std;
namespace {
const int N = 142;
vector<int64_t> dp;
pair<vector<int>, int> unrank(int64_t x) { // find the x-th sequence (0 indexed)
// if #(len1) = 5 and x=5 then we subtract
int len = 1;
while (x >= dp[len]) {
x -= dp[len++];
}
// find the ith sequence with this length
// order: nothing, 2, 3
int ans_len = len;
vector<int> ans;
while (len) {
// 5 sequences in cat A, 10 in cat B, 3 in cat C
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() {
// 2s are 1s, 3s are 0s
// sum 1 => {}
// sum 2 => {}, {2}
// sum 3 => {}, {2}, {3} (note that they aren't repeated and are distinguished by length)
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; // +1 means empty sequence
}
return N;
}
pair<vector<int>, vector<int>> Anna(long long A) {
auto [seq, len] = unrank(A);
vector<int> a;
int c = 1;
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) {
a.push_back(c = !c);
}
vector<int> b(a.size());
for (int i = 0; i < a.size(); i++) {
b[i] = (i + 1) & 1;
}
return {a, b};
}
#include <bits/stdc++.h>
using namespace std;
namespace {
const int N = 142;
vector<int64_t> dp;
int64_t rerank(vector<int> seq, int len) {
int64_t ans = 0;
for (int i = 1; i < len; ++i) {
ans += dp[i];
}
while (!seq.empty()) {
// dp[len] = 1 + dp[len-2] + dp[len-3]
// that is, either empty, or 2, or 3
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 { // == 3
ans += num_emp + num_2, len -= 3;
}
seq.pop_back();
}
return ans;
}
} // namespace
long long Bruno(vector<int> u) {
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 c = 1, sum = 0;
for (int &i : u) {
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);
}
