int arr[50];
 
int f(int a, int b=0) {
   if (b==-1) return 1;
   if (a==1) return 0;
   if (a==2) return 2;
   int r=f(a-2, arr[a-1]);
   int l=f(a-1, arr[a-2]);
   return (l+r);
}
 
int f2(int a, int b=0, int s=0) {
    for(;;) {
        if (b==-1) return s+1;
        if (a==1) return s;
        if (a==2) return s+2;
        s = f2(a-2, arr[a-1], s);
        b = arr[a-2];
        a = a-1;        
    }
}
 
#include <iostream>
#include <ctime>
int main() {
   clock_t begin = clock();
   int s=0;
   for(int i=1; i<41; ++i)
      s += f(i);
   clock_t diff = clock()-begin;
   std::cout << s << ':' << double(diff)/CLOCKS_PER_SEC << '\n';
 
   begin = clock();
   s=0;
   for(int i=1; i<41; ++i)
      s += f2(i);
   diff = clock()-begin;
   std::cout << s << ':' << double(diff)/CLOCKS_PER_SEC << '\n';
}

aW50IGFycls1MF07CgppbnQgZihpbnQgYSwgaW50IGI9MCkgewogICBpZiAoYj09LTEpIHJldHVybiAxOwogICBpZiAoYT09MSkgcmV0dXJuIDA7CiAgIGlmIChhPT0yKSByZXR1cm4gMjsKICAgaW50IHI9ZihhLTIsIGFyclthLTFdKTsKICAgaW50IGw9ZihhLTEsIGFyclthLTJdKTsKICAgcmV0dXJuIChsK3IpOwp9CgppbnQgZjIoaW50IGEsIGludCBiPTAsIGludCBzPTApIHsKICAgIGZvcig7OykgewogICAgICAgIGlmIChiPT0tMSkgcmV0dXJuIHMrMTsKICAgICAgICBpZiAoYT09MSkgcmV0dXJuIHM7CiAgICAgICAgaWYgKGE9PTIpIHJldHVybiBzKzI7CiAgICAgICAgcyA9IGYyKGEtMiwgYXJyW2EtMV0sIHMpOwogICAgICAgIGIgPSBhcnJbYS0yXTsKICAgICAgICBhID0gYS0xOyAgICAgICAgCiAgICB9Cn0KCiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGN0aW1lPgppbnQgbWFpbigpIHsKICAgY2xvY2tfdCBiZWdpbiA9IGNsb2NrKCk7CiAgIGludCBzPTA7CiAgIGZvcihpbnQgaT0xOyBpPDQxOyArK2kpCiAgICAgIHMgKz0gZihpKTsKICAgY2xvY2tfdCBkaWZmID0gY2xvY2soKS1iZWdpbjsKICAgc3RkOjpjb3V0IDw8IHMgPDwgJzonIDw8IGRvdWJsZShkaWZmKS9DTE9DS1NfUEVSX1NFQyA8PCAnXG4nOwoKICAgYmVnaW4gPSBjbG9jaygpOwogICBzPTA7CiAgIGZvcihpbnQgaT0xOyBpPDQxOyArK2kpCiAgICAgIHMgKz0gZjIoaSk7CiAgIGRpZmYgPSBjbG9jaygpLWJlZ2luOwogICBzdGQ6OmNvdXQgPDwgcyA8PCAnOicgPDwgZG91YmxlKGRpZmYpL0NMT0NLU19QRVJfU0VDIDw8ICdcbic7Cn0=