{-# OPTIONS -O2 #-}
import System.CPUTime (getCPUTime)
import Foreign (Ptr, peekElemOff, pokeElemOff, mallocArray)
import Control.Monad (forM_)
import System.Exit (exitFailure)

pushDown :: Ptr Int -> Int -> Int -> IO ()
pushDown h pos n
  | 2*pos + 1 < n = do
      let j' = 2*pos + 1
      atJ' <- peekElemOff h j'
      (j, atJ) <- if j'+1<n
                  then do atJ'inc <- peekElemOff h (j'+1)
                          return $ if atJ'inc > atJ'
                                   then (j'+1, atJ'inc)
                                   else (j', atJ')
                  else return (j', atJ')
      atPos <- peekElemOff h pos
      if atPos >= atJ
      then return ()
      else do pokeElemOff h j atPos
              pokeElemOff h pos atJ
              pushDown h j n
  | otherwise = return ()

main = do
  start <- getCPUTime
  let n = 10000000
  h <- mallocArray n
  forM_ [0..n-1] $ \i -> pokeElemOff h i i
  forM_ [n`div`2,n`div`2-1..0] $ \i -> pushDown h i n
  forM_ [n-1,n-2..1] $ \i -> do
         x <- peekElemOff h 0
         peekElemOff h i >>= pokeElemOff h 0
         pokeElemOff h i x
         pushDown h 0 i
  forM_ [0..n-1] $ \i -> do x <- peekElemOff h i
                            if i == x then return () else exitFailure
  end <- getCPUTime
  putStrLn $ "Done in " ++ (show $ (end - start) `div` 10^9)