import Data.Array type Board = Array Int Int main = do n <- read <$> getLine :: IO Int putStrLn $ show $ calcMinDist n updateBoard :: ([Int],Board) -> ([Int],Board) updateBoard ([],b) = ([],b) updateBoard (is,b) = (is',(b//if b!i'<0 then [] else prev ++ next)) where (_,n) = bounds b numOfOne = sum . map (`mod`2) . takeWhile (>0) . iterate (`div`2) pr = i' - numOfOne i' nx = i' + numOfOne i' prev = if pr<1 || (b!pr>=0&&b!prn || (b!nx>=0&&b!nx=0 && b!i<=b!i') then (i,i':is') else (i',i:is') calcMinDist :: Int -> Int calcMinDist n = snd (ntimes n updateBoard ([1..n],board)) ! n where board = listArray (1,n) $ 1:repeat (-1) ntimes 0 f x = x ntimes n f x = ntimes (n-1) f (f x)