#include"Anna.h"
#include<bits/stdc++.h>
typedef long long LL;
typedef std::vector<int> VI;
namespace {
const int N = 150;
LL f[N];
}
int Declare(){
	f[1] = f[2] = 1;
	for(int i = 3;i < N;++ i)
		f[i] = f[i-2] + f[i-3] + 1;
	return 140;
}
std::pair<VI, VI> Anna(LL k){
	-- k; int flg = k & 1; k >>= 1;
	int len = 1; while(k >= f[len]) k -= f[len++];
	VI s, t(len); s.reserve(len);
	int fl = flg; s.push_back(fl);
	for(int i = len;k;){
		if(k <= f[i-2]){-- k; i -= 2;}
		else {s.push_back(fl ^= 1); k -= f[i-2] + 1; i -= 3;}
		s.push_back(fl); s.push_back(fl);
	}
	while(s.size() < len) s.push_back(fl ^= 1);
	for(int i = 0;i < len;++ i) t[i] = flg ^ (i & 1);
	return std::make_pair(s, t);
}

#include"Bruno.h"
#include<bits/stdc++.h>
typedef long long LL;
typedef std::vector<int> VI;
namespace {
const int N = 150;
LL f[N];
}
LL Bruno(VI u){
	if(!f[1]){
		f[1] = f[2] = 1;
		for(int i = 3;i < N;++ i)
			f[i] = f[i-2] + f[i-3] + 1;
	}
	LL ans = 0; int len = u.size() >> 1;
	for(int i = 1;i < len;++ i) ans += f[i];
	int flg = u[0], fl = flg, sum = 0;
	for(int i = 1, j = len;i < u.size();++ i){
		sum += 2 * u[i] - 1;
		if(abs(sum) == 2){
			if((sum == 2) == fl){++ ans; j -= 2;}
			else {ans += f[j-2] + 1; j -= 3;}
			fl = sum == 2; sum = 0;
		}
	}
	return ans * 2 + flg + 1;
}