{-# LANGUAGE OverloadedStrings #-}

module Main where

import           Control.Applicative
import           Control.Monad
import           Control.Monad.State
import           Data.Array
import           Data.Array.Base
import           Data.Array.IO
import           Data.ByteString.Lazy.Char8 (ByteString)
import qualified Data.ByteString.Lazy.Char8 as BS
import           Data.Char
import           Data.IORef
import           Data.List             hiding (insert)
import           Data.Maybe

type Index = Int
type Item = Int
type Buffer = IOUArray Index Item
type Size = IORef Int
type Capacity = Int
data Heap = Heap Capacity Size Buffer

cmp :: Buffer -> Index -> Index -> IO Ordering
cmp buffer i j = liftM2 compare (unsafeRead buffer i) (unsafeRead buffer j)

swap :: Buffer -> Index -> Index -> IO ()
swap buffer i j = do
    a <- unsafeRead buffer i
    b <- unsafeRead buffer j
    unsafeWrite buffer i b
    unsafeWrite buffer j a

upheap :: Buffer -> Index -> IO ()
upheap buffer current
  | current <= 0 = return ()
  | otherwise = do
      t <- cmp buffer parent current
      when(t == LT) $ do
        swap buffer parent current
        upheap buffer parent
  where
    parent = (current - 1) `div` 2

downheap :: Buffer -> Int -> Index -> IO ()
downheap buffer size current
  | left >= size = return ()
  | otherwise = do
    son <- if right < size then cmp buffer left right >>= \t ->
              return (if t == LT then right else left)
           else return left
    t <- cmp buffer current son
    when(t == LT) $ do
      swap buffer current son
      downheap buffer size son
  where
    left = current * 2 + 1
    right = left + 1


makeHeap :: Capacity -> IO Heap
makeHeap n = do
  buffer <- newArray_ (0, n - 1)
  size <- newIORef 0
  return (Heap n size buffer)

fromList :: [Int] -> IO Heap
fromList xs = do
  let n = length xs
      half = n `div` 2 - 1
  buffer <- newListArray (0, n - 1) xs
  size <- newIORef n
  mapM_ (downheap buffer n) [half, half-1 .. 0]
  return (Heap n size buffer)

insert :: Heap -> Item -> IO ()
insert (Heap capacity size buffer) x = do
  current <- readIORef size
  if current >= capacity then error "Full Heap"
  else do
      unsafeWrite buffer current x
      writeIORef size (current + 1)
      upheap buffer current

extract :: Heap -> IO Item
extract (Heap _ size buffer) = do
  current <- readIORef size
  if current <= 0 then error "Empty Heap"
  else do
      x <- unsafeRead buffer 0
      writeIORef size (current - 1)
      when (current - 1 > 0) $ do
        swap buffer (current - 1) 0
        downheap buffer (current - 1) 0
      return x

isEmpty :: Heap -> IO Bool
isEmpty (Heap _ size _) = do
  current <- readIORef size
  return (current == 0)

isFull :: Heap -> IO Bool
isFull (Heap capacity size _) = do
  current <- readIORef size
  return (current == capacity)


readInt :: ByteString -> Int
readInt = fst . fromJust . BS.readInt


output:: Heap -> IO ()
output heap = do
  empty <- isEmpty heap
  unless empty $ do
    BS.putStr " "
    BS.putStr . BS.pack . show =<< extract heap
    output heap

main:: IO ()
main = do
  [_, num] <- map (map readInt. BS.words) . BS.lines <$> BS.getContents
  heap <- fromList num
  output heap
  BS.putStrLn ""


