@cache = []
def Q(n)
  if @cache[n].nil?
    case n
    when 1, 2 then @cache[n] = 1
    else @cache[n] = Q(n - Q(n-1)) + Q(n - Q(n-2))
    end
  end
  @cache[n]
end

puts 
puts  

prev = Q(1)
count = 0
2.upto(100_000) do |n| 
  q = Q(n)
  count += 1 if q < prev 
  prev = q
end
puts