#include <algorithm>
#include <cstdio>
#include <cstring>
#include <deque>
#include <vector>
using namespace std;

struct FimoSeq
{
  struct FirstHalf
  {
    deque< int > data;
    deque< int > MAX, MIN;

    void add(int x)
    {
      data.push_back(x);

      if (data.size() == 1)
      {
        MAX.push_back(x);
        MIN.push_back(x);
      }
      else
      {
        if (MAX.back() < x)
          MAX.push_back(x);
        if (MIN.back() > x)
          MIN.push_back(x);
      }
    }

    int remove()
    {
      int x = data.back();
      data.pop_back();

      if (MIN.back() == x)
        MIN.pop_back();
      if (MAX.back() == x)
        MAX.pop_back();

      return x;
    }

    int size() const { return data.size(); }
  } fh;

  struct LatterHalf
  {
    deque< int > data;
    deque< int > MAX, MIN;

    void add(int x)
    {
      data.push_back(x);

      if (data.size() == 1)
      {
        MAX.push_back(x);
        MIN.push_back(x);
      }
      else
      {
        while (!MAX.empty() && MAX.back() < x)
          MAX.pop_back();
        while (!MIN.empty() && MIN.back() > x)
          MIN.pop_back();

        MAX.push_back(x);
        MIN.push_back(x);
      }
    }

    int remove()
    {
      int x = data.front();
      data.pop_front();

      if (MIN.front() == x)
        MIN.pop_front();
      if (MAX.front() == x)
        MAX.pop_front();

      return x;
    }

    int size() const { return data.size(); }
  } lh;

  int size() { return fh.size() + lh.size(); }

  void add(int x)
  {
    lh.add(x);
    if (lh.size() > fh.size())
      fh.add(lh.remove());
  }

  int remove()
  {
    int r = fh.remove();
    if (lh.size() > fh.size())
      fh.add(lh.remove());

    return r;
  }

  int min_first_half(int i) { return *(fh.MIN.end() - i); }

  int min_latter_half(int i) { return *(lh.MIN.begin() + i - 1); }

  int max_first_half(int i) { return *(fh.MAX.end() - i); }

  int max_latter_half(int i) { return *(lh.MAX.begin() + i - 1); }
};

int main()
{
  while (true)
  {
    int Q;
    scanf("%d", &Q);
    if (Q == 0)
      break;

    FimoSeq fimo;

    for (int i = 0; i < Q; i++)
    {
      int q, x;
      scanf("%d", &q);

      switch (q)
      {
        case 0:
          scanf("%d", &x);
          fimo.add(x);
          break;
        case 1:
          printf("%d\n", fimo.remove());
          break;
        case 2:
          printf("%d\n", fimo.min_first_half(1));
          break;
        case 3:
          printf("%d\n", fimo.min_latter_half(1));
          break;
        case 4:
          scanf("%d", &x);
          printf("%d\n", fimo.min_first_half(x));
          break;
        case 5:
          scanf("%d", &x);
          printf("%d\n", fimo.min_latter_half(x));
          break;
        case 6:
          printf("%d\n", fimo.max_first_half(1));
          break;
        case 7:
          printf("%d\n", fimo.max_latter_half(1));
          break;
        case 8:
          scanf("%d", &x);
          printf("%d\n", fimo.max_first_half(x));
          break;
        case 9:
          scanf("%d", &x);
          printf("%d\n", fimo.max_latter_half(x));
          break;
      }
    }

    printf("end\n");
  }
  return 0;
}



Measured memory_bytes: 2908