### classes

class FH
  def initialize
    @data = []
    @mins = []
    @maxs = []
  end

  def size
    @data.length
  end

  def add(n)
    if @data.empty?
      @mins << n
      @maxs << n
    else
      @mins << n if @mins.last > n
      @maxs << n if @maxs.last < n
    end

    @data << n
  end

  def remove
    d = @data.pop
    @mins.pop if @mins.last == d
    @maxs.pop if @maxs.last == d
    d
  end

  def mins
    @mins
  end

  def maxs
    @maxs
  end
end

class SH
  def initialize
    @data = []
    @mins = []
    @maxs = []
  end

  def size
    @data.length
  end

  def add(n)
    if @data.empty?
      @mins << n
      @maxs << n
    else
      while ! @mins.empty? && @mins.last > n
        @mins.pop
      end
      @mins << n

      while ! @maxs.empty? && @maxs.last < n
        @maxs.pop
      end
      @maxs << n
    end

    @data << n
  end

  def remove
    d = @data.shift
    @mins.shift if @mins.first == d
    @maxs.shift if @maxs.first == d
    d
  end

  def mins
    @mins
  end

  def maxs
    @maxs
  end
end

class FIMO
  def initialize
    @fh = FH.new
    @sh = SH.new
  end

  def size
    @fh.size + @sh.size
  end

  def add(n)
    @sh.add(n)
    if @fh.size < @sh.size
      @fh.add(@sh.remove)
    end
  end

  def remove
    d = @fh.remove
    if @fh.size < @sh.size
      @fh.add(@sh.remove)
    end
    d
  end

  def fhmin(i)
    @fh.mins[-i]
  end

  def shmin(i)
    @sh.mins[i - 1]
  end

  def fhmax(i)
    @fh.maxs[-i]
  end

  def shmax(i)
    @sh.maxs[i - 1]
  end
end

### main

loop do
  qn = gets.to_i
  break if qn == 0

  fimo = FIMO.new

  qn.times do
    op, num = gets.split.map(&:to_i)
    #p [op, num]

    case op
    when 0
      fimo.add(num)
    when 1
      puts fimo.remove
    when 2
      puts fimo.fhmin(1)
    when 3
      puts fimo.shmin(1)
    when 4
      puts fimo.fhmin(num)
    when 5
      puts fimo.shmin(num)
    when 6
      puts fimo.fhmax(1)
    when 7
      puts fimo.shmax(1)
    when 8
      puts fimo.fhmax(num)
    when 9
      puts fimo.shmax(num)
    end
  end

  #p as
  puts 'end'
end