
import           Control.Applicative
import           Control.Monad
import           Data.List           hiding (insert, union)
import           Data.Maybe
import           Text.Printf

data SkewHeap a = Empty
                | Node a (SkewHeap a) (SkewHeap a)

singleton :: Ord a => a -> SkewHeap a
singleton x = Node x Empty Empty

union :: Ord a => SkewHeap a -> SkewHeap a -> SkewHeap a
Empty              `union` t2                 = t2
t1                 `union` Empty              = t1
t1@(Node x1 l1 r1) `union` t2@(Node x2 l2 r2)
   | x1 >= x2                                 = Node x1 (t2 `union` r1) l1
   | otherwise                                = Node x2 (t1 `union` r2) l2

insert :: Ord a => a -> SkewHeap a -> SkewHeap a
insert x heap = singleton x `union` heap

extractMax :: Ord a => SkewHeap a -> Maybe (a, SkewHeap a)
extractMax Empty        = Nothing
extractMax (Node x l r) = Just (x, l `union` r)

main = do
    cmds<- (takeWhile (/= "end") . lines) <$> getContents
    putStr $ unlines $ map show $ snd $ foldl operate (Empty, []) (map words cmds)
      where
        operate::(SkewHeap Int, [Int]) -> [String] -> (SkewHeap Int,[Int])
        operate (heap, result) ["insert", val] = (insert (read val) heap, result)
        operate (heap, result) ["extract"]
          | isJust m = (snd (fromJust m), result++[fst (fromJust m)])
          | otherwise = (Empty, result)
              where
                m = extractMax heap

