import qualified Data.Array
import Data.Word
import Data.List
import Data.Array.ST
import Data.Array.MArray
import Control.Monad.ST
import Control.Monad
import Data.Array.IArray

upperbound = 1000000

collatz_array_mutable =
  runSTUArray ( do
    arr <- newArray (1, upperbound) maxBound :: ST s (STUArray s Word64 Word16)
    writeArray arr 1 0
    forM_ [1..upperbound] (\i -> 
      do
        {
          let
            next_i i = f ((if (even i) then i else 3 * i + 1) `div` 2)
            f i = 
              do
                if i > upperbound
                 then
                  do
                    new_elem <- next_i i
                    return (new_elem + 1)
                 else
                  do
                    elem <- readArray arr i
                    if elem == maxBound
                     then
                      do
                        new_elem <- next_i i
                        writeArray arr i (new_elem + 1)
                        return (new_elem + 1)
                     else
                      return elem
          in
            f i
        }
      )
    return arr
  )
  
main = 
  putStrLn $ show $ 
    foldl1' (\(x1,x2) (y1,y2) -> if (x2 >= y2) then (x1, x2) else (y1, y2)) $! (assocs collatz_array_mutable)