### main

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

  as = []

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

    im = (as.length + 1) / 2

    case op
    when 0
      as << num
    when 1
      puts as.delete_at(im - 1)
    when 2
      puts as[0...im].min
    when 3
      puts as[im...as.length].min
    when 4
      as0 = (0...as.length).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
      puts mins.uniq.sort[num - 1]
    when 5
      as0 = (0...as.length).map{|i| [as[i], i >= im]}
      mins = []
      while ! as0.empty?
        im0 = (as0.length + 1) / 2
        i0 = (im0...as0.length).min{|a, b| as0[a][0] <=> as0[b][0]}
        mins << as0[i0][0] if i0 && as0[i0][1]
        as0.delete_at(im0 - 1)
      end
      puts mins.uniq.sort[num - 1]
    when 6
      puts as[0...im].max
    when 7
      puts as[im...as.length].max
    when 8
      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
      puts maxs.uniq.sort[-num]
    when 9
      as0 = (0...as.length).map{|i| [as[i], i >= im]}
      maxs = []
      while ! as0.empty?
        im0 = (as0.length + 1) / 2
        i0 = (im0...as0.length).max{|a, b| as0[a][0] <=> as0[b][0]}
        maxs << as0[i0][0] if i0 && as0[i0][1]
        as0.delete_at(im0 - 1)
      end
      puts maxs.uniq.sort[-num]
    end
  end

  #p as
  puts 'end'
end