### main

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

  as = []
  aslen = 0

  fhmins = []
  fhmaxs = []
  lhmins = []
  lhmaxs = []

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

    im = (as.length + 1) / 2

    case op
    when 0
      as << num
      aslen += 1
      fhmins = []
      fhmaxs = []
      lhmins = []
      lhmaxs = []
    when 1
      puts as.delete_at(im - 1)
      fhmins = []
      fhmaxs = []
      lhmins = []
      lhmaxs = []
    when 2
      if fhmins.empty?
        puts as[0...im].min
      else
        puts fhmins.first
      end
    when 3
      if lhmins.empty?
        puts as[im...aslen].min
      else
        puts lhmins.last
      end
    when 4
      if fhmins.empty?
        as0 = (0...aslen).map{|i| [as[i], i < im]}
        mins = []
        while ! as0.empty?
          im0 = (as0.length + 1) / 2
          i0 = (0...im0).min{|a, b| as0[a][0] <=> as0[b][0]}
          mins << as0[i0][0] if i0 && as0[i0][1]
          as0.delete_at(im0 - 1)
        end
        fhmins = mins.uniq.sort
      end
      puts fhmins[num - 1]
    when 5
      if lhmins.empty?
        min0 = as.last
        lhmins = [min0]
        (aslen - 2).downto(im) do |k|
          if min0 > as[k]
            min0 = as[k]
            lhmins << min0
          end
        end
      end
      puts lhmins[-num]
    when 6
      if fhmaxs.empty?
        puts as[0...im].max
      else
        puts fhmaxs.first
      end
    when 7
      if lhmaxs.empty?
        puts as[im...aslen].max
      else
        puts lhmaxs.last
      end
    when 8
      if fhmaxs.empty?
        as0 = (0...as.length).map{|i| [as[i], i < im]}
        maxs = []
        while ! as0.empty?
          im0 = (as0.length + 1) / 2
          i0 = (0...im0).max{|a, b| as0[a][0] <=> as0[b][0]}
          maxs << as0[i0][0] if i0 && as0[i0][1]
          as0.delete_at(im0 - 1)
        end
        fhmaxs = maxs.uniq.sort{|a, b| b <=> a}
      end
      puts fhmaxs[num - 1]
    when 9
      if lhmaxs.empty?
        max0 = as.last
        lhmaxs = [max0]
        (aslen - 2).downto(im) do |k|
          if max0 < as[k]
            max0 = as[k]
            lhmaxs << max0
          end
        end
      end
      puts lhmaxs[-num]
    end
  end

  #p as
  puts 'end'
end