#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

int main() {
  int n;
  while(cin>>n,n) {
    deque<int> a;               // O¼ªðO©ç©½ñ
    deque<int> b;               // ã¼ªðãë©ç©½ñ
    deque<int> min1;            // min1[i] = NG4Ì¦
    deque<int> min2;            // min2[i] = NG5Ì¦
    deque<int> max1;            // max1[i] = NG8Ì¦
    deque<int> max2;            // max2[i] = NG9Ì¦
    int m = 0;
    REP(i, n) {
      int q, x;
      cin >> q;
      if (q == 0) {
        cin >> x;
        if (m % 2) {
          b.push_front(x);
          while(min2.size() && min2[min2.size()-1] > x) min2.pop_back();
          min2.push_back(x);
          while(max2.size() && max2[max2.size()-1] < x) max2.pop_back();
          max2.push_back(x);
        } else {
          int y;
          if (m == 0) {
            a.push_back(x);
            y = x; x = -1;
          } else {
            b.push_front(x);
            y = b[b.size()-1];
            a.push_back(y);
            b.pop_back();
            if (min2.size() && min2[0] == y)
              min2.pop_front();
            if (max2.size() && max2[0] == y)
              max2.pop_front();
            while(min2.size() && min2[min2.size()-1] > x) min2.pop_back();
            min2.push_back(x);
            while(max2.size() && max2[max2.size()-1] < x) max2.pop_back();
            max2.push_back(x);
          }
          if (min1.empty() || y < min1[0])
            min1.push_front(y);
          if (max1.empty() || y > max1[0])
            max1.push_front(y);
        }
        m++;
      } else if (q == 1) {
        x = a[a.size()-1];
        a.pop_back();
        if (min1.size() && min1[0] == x)
          min1.pop_front();
        if (max1.size() && max1[0] == x)
          max1.pop_front();
        cout << x << endl;
        if (m % 2 == 0) {
          int y = b[b.size()-1];
          a.push_back(y);
          b.pop_back();
          if (min2.size() && min2[0] == y)
            min2.pop_front();
          if (max2.size() && max2[0] == y)
            max2.pop_front();
          if (min1.empty() || y < min1[0])
            min1.push_front(y);
          if (max1.empty() || y > max1[0])
            max1.push_front(y);
        }
        m--;
      } else if (q == 2) {
        cout << min1[0] << endl;
      } else if (q == 3) {
        cout << min2[0] << endl;
      } else if (q == 4) {
        cin >> x;x--;
        cout << min1[x] << endl;
      } else if (q == 5) {
        cin >> x;x--;
        cout << min2[x] << endl;
      } else if (q == 6) {
        cout << max1[0] << endl;
      } else if (q == 7) {
        cout << max2[0] << endl;
      } else if (q == 8) {
        cin >> x;x--;
        cout << max1[x] << endl;
      } else {
        cin >> x;x--;
        cout << max2[x] << endl;
      }

      // cout << "a = "; FOR(it, a) cout << *it << " "; cout << endl;
      // cout << "b = "; FOR(it, b) cout << *it << " ";cout << endl;
      // // cout << "min1 = "; FOR(it, min1) cout << *it << " ";cout << endl;
      // // cout << "min2 = "; FOR(it, min2) cout << *it << " ";cout << endl;
      // // cout << "max1 = "; FOR(it, max1) cout << *it << " ";cout << endl;
      // cout << "max2 = "; FOR(it, max2) cout << *it << " ";cout << endl;
      
    }
    cout << "end" << endl;
  }
}

Measured memory_bytes: 1080