      lastSpoken = prefix `zip` [1..] & Map.fromList  -- number -> turn spoken
  in locate (length input & fromIntegral) (last input) lastSpoken
  where
    locate :: Integer -> Integer -> Map.Map Integer Integer -> Integer
    locate thisTurn aboutToSay lastSpoken
      | thisTurn == n = aboutToSay
      | otherwise =
                    let  previously = Map.lookup aboutToSay lastSpoken
                         nextToSay = case previously of
                                       Nothing -> 0
                                       Just lastTurn -> thisTurn - lastTurn
                    in   locate (thisTurn + 1) nextToSay (Map.insert aboutToSay thisTurn lastSpoken)
