#include <iostream>
#include <vector>
using namespace std;
 
class Solution {
public:
    int magicalString(int n) {
        vector<int> a={1,2,2,1}, b;
        while(a.size()<100000){
            b.clear();
            int num=1;
            for(int i=0; i<a.size(); ++i){
                for(int r=0; r<a[i]; ++r) b.push_back(num);
                num=3-num;
            }
            a = b;
        }
        int res=0;
        for(int i=0; i<n; ++i) res+=(a[i]==1);
        return res;
    }
};
 
int main() {
	Solution s;
	cout<<s.magicalString(100000)<<endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgU29sdXRpb24gewpwdWJsaWM6CiAgICBpbnQgbWFnaWNhbFN0cmluZyhpbnQgbikgewogICAgICAgIHZlY3RvcjxpbnQ+IGE9ezEsMiwyLDF9LCBiOwogICAgICAgIHdoaWxlKGEuc2l6ZSgpPDEwMDAwMCl7CiAgICAgICAgICAgIGIuY2xlYXIoKTsKICAgICAgICAgICAgaW50IG51bT0xOwogICAgICAgICAgICBmb3IoaW50IGk9MDsgaTxhLnNpemUoKTsgKytpKXsKICAgICAgICAgICAgICAgIGZvcihpbnQgcj0wOyByPGFbaV07ICsrcikgYi5wdXNoX2JhY2sobnVtKTsKICAgICAgICAgICAgICAgIG51bT0zLW51bTsKICAgICAgICAgICAgfQogICAgICAgICAgICBhID0gYjsKICAgICAgICB9CiAgICAgICAgaW50IHJlcz0wOwogICAgICAgIGZvcihpbnQgaT0wOyBpPG47ICsraSkgcmVzKz0oYVtpXT09MSk7CiAgICAgICAgcmV0dXJuIHJlczsKICAgIH0KfTsKCmludCBtYWluKCkgewoJU29sdXRpb24gczsKCWNvdXQ8PHMubWFnaWNhbFN0cmluZygxMDAwMDApPDxlbmRsOwoJcmV0dXJuIDA7Cn0=