{-# LANGUAGE OverloadedStrings #-}

import           Control.Applicative
import           Control.Monad
import qualified Data.ByteString.Char8 as B

import           Data.Array.IArray
import           Data.Array.IO
import           Data.Array.MArray

readi :: B.ByteString -> Int
readi b | Just (n, _) <- B.readInt b = n

data MaxHeap = MaxHeap !Int !(IOUArray Int Int)

emptyHeap :: Int -> IO MaxHeap
emptyHeap size = do
    arr <- newArray (0, size) minBound
    return $ MaxHeap 0 arr

buildMaxHeap :: Int -> MaxHeap -> IO ()
buildMaxHeap n h = do
    let e = n `div` 2
    forM_ [e, e-1 .. 1] $ \i -> do
        maxHeapify i h

maxHeapify :: Int -> MaxHeap -> IO ()
maxHeapify i h@(MaxHeap n arr) = do
    let is = filter (<= n) [i, i * 2, i * 2 + 1]
    vs <- sequence $ fmap (readArray arr) is
    let (_, maxi) = maximum (zip vs is)
    when (maxi /= i) $ do
        swap i maxi arr
        maxHeapify maxi h

swap :: Int -> Int -> IOUArray Int Int -> IO ()
swap i j arr = do
    vi <- readArray arr i
    vj <- readArray arr j
    writeArray arr i vj
    writeArray arr j vi

insert :: Int -> MaxHeap -> IO MaxHeap
insert k (MaxHeap n arr) = do
    writeArray arr (n + 1) k
    bubbleUp (n + 1) arr
    return $ MaxHeap (n + 1) arr

bubbleUp :: Int -> IOUArray Int Int -> IO ()
bubbleUp i arr = do
    let p = i `div` 2
    when (p >= 1) $ do
        vi <- readArray arr i
        vp <- readArray arr p
        when (vi > vp) $ do
            swap i p arr
            bubbleUp p arr

extractMax :: MaxHeap -> IO (Int, MaxHeap)
extractMax (MaxHeap n arr) = do
    when (n <= 0) $ error "extract from empty heap"
    r <- readArray arr 1
    vn <- readArray arr n
    writeArray arr 1 vn
    let h = MaxHeap (n - 1) arr
    buildMaxHeap (n - 1) h
    return (r, h)

solve :: MaxHeap -> [[B.ByteString]] -> IO ()
solve _ [] = return ()
solve _ (["end"]:_) = return ()
solve h ([_]:xss) = do
    (n, h') <- extractMax h
    print n
    solve h' xss
solve h ([_, bn]:xss) = do
    let k = readi bn
    h' <- insert k h
    solve h' xss

main :: IO ()
main = do
    xss <- fmap B.words . B.lines <$> B.getContents
    heap <- emptyHeap 2000001
    solve heap xss

