module Problem692 where

import Data.Array

lim :: Int
-- lim = 23_416_728_348_467_685 = 2.34 x 10^15
lim = 23416728348467685

main :: IO ()
{-
 - caseof fibonacci nim - we need the last digit in fibonacci encoding
 - represent n as fibonacci encoding
 - will be of the form 101... where there is atleast one zero between any two 1s otherwise 
   we combine them to get next fibonacci number
 - so for nth fibonnaci we can have all zeros or fibonacci upto n-2
 - h(n) = f(n) + h(n-2) + h(n-1) + .. = f(n) + g(n-2)
 - g(n) = h(n) + g(n-1) = f(n) + g(n-1) + g(n-2)
 - also lim is a fibonacci number
-}
main = print $ g ! (n - 1) + last f
  where
    f  = takeWhile (<= lim) $ map fst $ iterate (\(a, b) -> (b, a + b)) (1, 2)
    n  = length f
    f' = listArray (1, n) f
    g  = listArray
        (1, n)
        (1 : 3 : [ g ! (i - 1) + g ! (i - 2) + f' ! i | i <- [3 ..] ])

