loop do
  q = gets.to_i
  break if q==0
  a = Array.new
  a.push(0)
  q.times do
    qur = gets.split.map(&:to_i)
    case qur[0]
    when 1
      #    1: このクエリーが与えられたら数列内の数を1つ消去する。 数列の真ん中の数が消去される。
      #      消去する数は,数列が n 個の値を持っているとすると数列の真ん中の数、 an/2 である。 n が奇数の場合は n/2 を切り上げしたものを利用してその数 a&#8968;n/2&#8969; を消去する。
      #      数列が空の場合にこのクエリーがくることはない。 例えば現在数列が a1 = 1 , a2 = 2 , a3 =3, a4 =4, a5 =5 だったとする。
      #      この場合 a3 が消去される。 その結果 a1 =1, a2 =2, a3 =4, a4 =5となる。 もう一つの例を示す。 数列が a1 =1, a2 =2, a3 =3, a4 =4 だったとする。 この状態で消去を行うと消去されるのは a2 =2で消去した後数列は a1 =1, a2 =3, a3 =4 となる。
      p a.delete_at(a.size/2)
    when 2
      #    このクエリーが与えられたら数列の前半部分に含まれる数の中から最小値が何か求める。 数列の前半部分が空の場合にこのクエリーがくることはない。
      p a[1..a.size/2].min
    when 3
      #  3: このクエリーが与えられたら数列の後半部分、つまり前半部分に属さない数の中から最小値が何かを求める。 数列の後半部分が空の場合にこのクエリーがくることはない。
      p (a[a.size/2+1..-1]).min
    when 4
      #4: このクエリーは数 i と一緒に与えられる。 現在の数列の状態から挿入を行わずに消去を続けたと仮定する。 現在前半部分に含まれる数の中からクエリー2の結果になる可能性があるものがいくつかある。
      #その中で i 番目に小さい数を求める。 数列の前半部分が空のときにこのクエリーがくることはない。また i 番目の要素は必ず存在すると仮定してよい。
      b = a.dup
      c = Array.new
      until b.empty?
        unless b[1..b.size/2].empty?
          c.push(b[1..b.size/2].min)
        end
        b.delete_at(b.size/2)
      end
      c &=a[1..a.size/2]
      c.sort!
      p c[qur[1]-1]
    when 5
      #現在後半部分に含まれる数字の中からクエリー3の結果になる可能性があるものがいくつかある。 その中で i 番目に小さい物を求める。
      b = a.dup
      c = Array.new
      until b.empty?
        unless (b[b.size/2+1..-1]).empty?
          c.push( (b[b.size/2+1..-1]).min)
        end
        b.delete_at(b.size/2)
      end
      c &=(a[a.size/2+1..-1])
      c.sort!
      p c[qur[1]-1]
    when 6
      #6: このクエリーが与えられたら数列の前半部分に含まれる数の中から最大の値が何か求める。 数列の前半部分が空の時、このクエリーは与えられない。
      p a[1..a.size/2].max
    when 7
      #7: このクエリーが与えられたら数列の後半部分に含まれる数の中から最大の値が何かを求める。 数列の前半部分が空の時、このクエリーは与えられない。
      p (a[a.size/2+1..-1]).max
    when 8
      #現在の数列の状態から挿入を行わずに消去を続けたと仮定する。
      #      現在前半部分に含まれる数の中からクエリー6の結果になる可能性があるものがいくつかある。 その中で i 番目に大きい数を求める。
      b = a.dup
      c = Array.new
      until b.empty?
        unless b[1..b.size/2].empty?
          c.push(b[1..b.size/2].max)
        end
        b.delete_at(b.size/2)
      end
      c &=a[1..a.size/2]
      c.sort!{|x,y|y-x}
      p c[qur[1]-1]
    when 9
      b = a.dup
      c = Array.new
      until b.empty?
        unless (b[b.size/2+1..-1]).empty?
          c.push((b[b.size/2+1..-1]).max)
        end
        b.delete_at(b.size/2)
      end
      c &=(a[a.size/2+1..-1])
      c.sort!{|x,y|y-x}
      p c[qur[1]-1]
    when 0
      #    0: このクエリーは数 x と一緒に与えられる。 このクエリーが与えられたら数列に数 x を挿入する。
      #     数列が空の時に挿入を行うと a1 = x となる。 数列が n 個の要素を持っている時に挿入を行うと an+1 = x となる。
      #      なおクエリーとして与えられる x は重複しないとする。
      a.push(qur[1])
    end
  end
  puts "end"
end