#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=