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)

go:: SkewHeap Int -> IO ()
go heap = do
  cmd <- getLine
  if cmd=="end" then return ()
  else do
    let params = words cmd
    case head params of
      "insert" -> go (insert (read $ last params) heap)
      "extract" -> do
          let m = extractMax heap
          if isJust m then do
            print $ fst (fromJust m)
            go $ snd (fromJust m)
          else go Empty
      _ -> return ()

main = go Empty
