import           Control.Applicative
import           Control.Monad
import           Data.Array.IO
import           Data.IORef
import           Data.List           hiding (insert, union)
import           Data.Maybe
import           GHC.Conc            (enableAllocationLimit,
                                      setAllocationCounter)
import           System.IO
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)

-}
{-
data Heap a = Empty | Heap a [Heap a]
    deriving Show

findMax :: Heap a -> a
findMax (Heap h _) = h

merge :: Ord a => Heap a -> Heap a -> Heap a
merge Empty h = h
merge h Empty = h
merge h1@(Heap x hs1) h2@(Heap y hs2)
    | x > y     = Heap x (h2:hs1)
    | otherwise = Heap y (h1:hs2)

mergePairs :: Ord a => [Heap a] -> Heap a
mergePairs []         = Empty
mergePairs [h]        = h
mergePairs (h1:h2:hs) = merge (merge h1 h2) (mergePairs hs)

insert :: Ord a => a -> Heap a -> Heap a
insert x = merge (Heap x [])

deleteMax :: Ord a => Heap a -> Heap a
deleteMax (Heap x hs) = mergePairs hs
-}

--
-- heap.hs : 配列を使ったヒープの実装
--
--            Copyright (C) 2013 Makoto Hiroi
--

-- データ型の定義
data Heap a = Heap Int (IORef Int) (IOArray Int a)

-- 要素の比較
compItem :: Ord a => IOArray Int a -> Int -> Int -> IO Ordering
compItem buff i j = liftM2 (compare) (readArray buff i) (readArray buff j)

-- 要素の交換
swapItem :: IOArray Int a -> Int -> Int -> IO ()
swapItem buff i j = do
  a <- readArray buff i
  b <- readArray buff j
  writeArray buff i b
  writeArray buff j a

-- ルート方向に向かってヒープを構築
upheap :: Ord a => IOArray Int a -> Int -> IO ()
upheap buff n = do
  when (n > 0) $ do
    let p = (n - 1) `div` 2
    t <- compItem buff p n
    when (t == LT) $ do
      swapItem buff p n
      upheap buff p

-- 葉の方向に向かってヒープを構築
downheap :: Ord a => IOArray Int a -> Int -> Int -> IO ()
downheap buff n h = iter n h
  where
    selectChild c1 h = do
      let c2 = c1 + 1
      if c2 > h
        then return c1
        else do
          t <- compItem buff c1 c2
          if t == LT
            then return c2
            else return c1
    iter n h = do
      let c1 = 2 * n + 1
      when (c1 <= h) $ do
        c <- selectChild c1 h
        t <- compItem buff n c
        when (t == LT) $ do
          swapItem buff n c
          iter c h

-- ヒープの生成
makeHeap :: Int -> IO (Heap a)
makeHeap n = do
  a <- newArray_ (0, n - 1)
  b <- newIORef 0
  return (Heap n b a)

-- リストからヒープを生成する
fromList :: Ord a => [a] -> IO (Heap a)
fromList xs = do
  let n = length xs
      m = n `div` 2 - 1
  a <- newListArray (0, n - 1) xs
  b <- newIORef n
  mapM_ (\x -> downheap a x (n - 1)) [m, m-1 .. 0]
  return (Heap n b a)

-- データの追加
insert :: Ord a => Heap a -> a -> IO ()
insert (Heap size cnt buff) x = do
  c <- readIORef cnt
  if c >= size
    then error "Full Heap"
    else do
      writeArray buff c x
      writeIORef cnt (c + 1)
      upheap buff c

-- 最大値を取り出す
deleteMax :: Ord a => Heap a -> IO a
deleteMax (Heap _ cnt buff) = do
  c <- readIORef cnt
  if c <= 0
    then error "Empty Heap"
    else do
      x <- readArray buff 0
      let c1 = c - 1
      writeIORef cnt c1
      when (c1 > 0) $ do
        swapItem buff 0 c1
        downheap buff 0 (c1 - 1)
      return x

-- 最大値を求める
findMax :: Ord a => Heap a -> IO a
findMax (Heap _ cnt buff) = do
  c <- readIORef cnt
  if c <= 0
    then error "Empty Heap"
    else readArray buff 0

-- ヒープは空か
isEmpty :: Heap a -> IO Bool
isEmpty (Heap _ cnt _) = do
  c <- readIORef cnt
  return (c == 0)

-- ヒープは満杯か
isFull :: Heap a -> IO Bool
isFull (Heap size cnt _) = do
  c <- readIORef cnt
  return (c == size)

main =
  do setAllocationCounter (131072*1024)
     enableAllocationLimit
     heap <- makeHeap 2000000
     loop heap
        where
           loop::Heap Int -> IO()
           loop heap = do
             cmd <- getLine
             if cmd=="end" then return ()
             else do
               let params = words cmd
               case head params of
                 "insert"  -> insert heap (read $ last params)
                 "extract" -> print =<< deleteMax heap
                 _         -> return ()
               loop heap

