// By Pedro Zanetti (PzanettiD on GitHub).

# include <iostream>
# include <vector>
using namespace std;

// Recursive implementation for generating the Hofstadter Q-sequence.
int hof_q_recursive(int n)
{
   if (n <= 2)
   {
      return 1;
   }
   else
   {
      return hof_q_recursive(n - hof_q_recursive(n-1)) + hof_q_recursive(n - hof_q_recursive(n-2));
   }
}

// Bottom-up implementation for generating the Hofstadter Q-sequence.
vector<int> hof_q_bup(int n)
{
   vector<int> mem;
   mem.push_back(0);
   mem.push_back(1);
   mem.push_back(1);
   for (int i = 3; i < n; i++)
   {
      mem[i] = mem[i - mem[i-1]] + mem[i - mem[i-2]];
   }
   return mem;
}