/*
 * AOJ 1070: FIMO sequence
 * ?¢???????????§???????????????????10?§??????????????°??????\???????????°????????°???????????°??????????±?????????????????????§????°??????????????????????????????°?????????????¬????????????????????????????????????§????°??????°????±???¶????¬¬i??§??????
 * ?±???????????????????
 * ???????????´???6???????????????????????????????????°??????????°???????????°?????????????????????????????????????????????°??????????°±?????´?°??????\?????´?°?????????????????????????
 */

#include <cstdio>

const int MAXN = 200010;

int la[MAXN], ls[MAXN], lb[MAXN], ra[MAXN], rs[MAXN], rb[MAXN];
int la1, la2, ls1, ls2, lb1, lb2, ra1, ra2, rs1, rs2, rb1, rb2, m;

void outall() {
  printf("----outall----\n");
  for (int i = la1; i < la2; ++i) {
    printf("%d ", la[i]);
  }
  printf("\n");
  for (int i = ls1; i < ls2; ++i) {
    printf("%d ", ls[i]);
  }
  printf("\n");
  for (int i = lb1; i < lb2; ++i) {
    printf("%d ", lb[i]);
  }
  printf("\n");
  for (int i = ra1; i < ra2; ++i) {
    printf("%d ", ra[i]);
  }
  printf("\n");
  for (int i = rs1; i < rs2; ++i) {
    printf("%d ", rs[i]);
  }
  printf("\n");
  for (int i = rb1; i < rb2; ++i) {
    printf("%d ", rb[i]);
  }
  printf("\n");
  printf("\n");
}

void left_push_back(int x) {
  la[la2++] = x;
  if (ls2 == ls1 || ls[ls2 - 1] > x) {
    ls[ls2++] = x;
  }
  if (lb2 == lb1 || lb[lb2 - 1] < x) {
    lb[lb2++] = x;
  }
}

void right_push_back(int x) {
  ra[ra2++] = x;
  while (rs2 > rs1 && rs[rs2 - 1] > x) {
    --rs2;
  }
  rs[rs2++] = x;
  while (rb2 > rb1 && rb[rb2 - 1] < x) {
    --rb2;
  }
  rb[rb2++] = x;
}

int right_pop_front() {
  if (ra[ra1] == rs[rs1]) ++rs1;
  if (ra[ra1] == rb[rb1]) ++rb1;
  ++ra1;
  return ra[ra1 - 1];
}

int left_pop_back() {
  if (la[la2 - 1] == ls[ls2 - 1]) --ls2;
  if (la[la2 - 1] == lb[lb2 - 1]) --lb2;
  --la2;
  return la[la2];
}

void f0_add() {
  int x;
  scanf("%d", &x);
  if (m == 0) {
    left_push_back(x);
  } else {
    right_push_back(x);
    if (!(m & 1)) {
      int y = right_pop_front();
      left_push_back(y);
    }
  }
  ++m;
//  outall();
}

void f1_del() {
  int x = left_pop_back();
  printf("%d\n", x);
  if (!(m & 1)) {
    int y = right_pop_front();
    left_push_back(y);
  }
  --m;
}

void f2_ls() {
  int x = ls[ls2 - 1];
  printf("%d\n", x);
}

void f3_rs() {
  int x = rs[rs1];
  printf("%d\n", x);
}

void f4_ls_() {
  int i, x;
  scanf("%d", &i);
  x = ls[ls2 - i];
  printf("%d\n", x);
}

void f5_rs_() {
  int i, x;
  scanf("%d", &i);
  x = rs[rs1 + i - 1];
  printf("%d\n", x);
}

void f6_lb() {
  int x = lb[lb2 - 1];
  printf("%d\n", x);
}

void f7_rb() {
  int x = rb[rb1];
  printf("%d\n", x);
}

void f8_lb_() {
  int i, x;
  scanf("%d", &i);
  x = lb[lb2 - i];
  printf("%d\n", x);
}

void f9_rb_() {
  int i, x;
  scanf("%d", &i);
  x = rb[rb1 + i - 1];
  printf("%d\n", x);
}

int main() {
//  freopen("/Users/yogy/acm-challenge-workbook/db.in", "r", stdin);
  int n;
  while (scanf("%d", &n) != EOF && n) {
    m = la1 = la2 = ls1 = ls2 = lb1 = lb2 = ra1 = ra2 = rs1 = rs2 = rb1 = rb2 = 0;
    while (n--) {
      int t;
      scanf("%d", &t);
//      printf("type = %d\n", t);
      switch (t) {
        case 0:
          f0_add();
          break;
        case 1:
          f1_del();
          break;
        case 2:
          f2_ls();
          break;
        case 3:
          f3_rs();
          break;
        case 4:
          f4_ls_();
          break;
        case 5:
          f5_rs_();
          break;
        case 6:
          f6_lb();
          break;
        case 7:
          f7_rb();
          break;
        case 8:
          f8_lb_();
          break;
        case 9:
          f9_rb_();
          break;
      }
    }
    printf("end\n");
  }
  return 0;
}

Measured memory_bytes: 2988