#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <bitset>
#include <stack>
#include <random>
#include <fstream>
#include <sstream>
#include <chrono>

template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;}

using namespace std;

const int maxn = 2e5 + 20;

ostream& operator << (ostream& out, const pair<int, int>& v) {
 out << v.first << ", " << v.second;
 return out;
}

template<typename T> ostream& operator << (ostream& out, const vector<T>& v) {
    for (auto& x: v) out << x << " ";
    return out;
}

istream& operator >> (istream& in, pair<int, int>& a) {
 in >> a.first >> a.second;
 return in;
}

const long long inf = (long long) 2e9;
const long double pi = asin (1) * 2;
const long double eps = 1e-8;
const long long mod = (long long)1e9 + 7;
const long long ns = 97;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

struct tree {
 vector<int> t;
 int size = 0, capacity;

 tree (int n) {
  while ((1<<size) < n) ++size;
  ++size;
  size = (1<<size);
  capacity = (size>>1);
  t = vector<int> (size);
 }

 int get (int cur, int k) {
  if (cur * 2 >= size) return cur - capacity;
  if (t[cur * 2] >= k) return get (cur * 2, k);
  return get (cur * 2 + 1, k - t[cur * 2]);
 }

 void add (int i, int x) {
  i += capacity;
  t[i] += x;
  i >>= 1;
  while (i) {
   t[i] = t[i * 2] + t[i * 2 + 1];
   i >>= 1;
  }
 }
};

signed main () {
 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);
 cout.tie(nullptr);
 int n;
 cin >> n;
 vector<pair<int, int> > kek;
 for (int i = 0; i < n; ++i) {
  string t;
  int x = 0;
  cin >> t;
  if (t == "add") {
   cin >> x;
   kek.push_back ({0, x});
  }
  if (t == "min") kek.push_back ({1, x});
  if (t == "max") kek.push_back ({2, x});
  if (t == "mid") kek.push_back ({3, x});
 }
 vector<int> tmp;
 for (auto& x: kek) tmp.push_back (x.second);
 sort (tmp.begin(), tmp.end());
 tmp.resize (unique (tmp.begin(), tmp.end()) - tmp.begin ());
 for (auto& x: kek) x.second = (int)(lower_bound (tmp.begin(), tmp.end(), x.second) - tmp.begin ());
 int m = (int)tmp.size();
 tree goo (m);
 int cnt = 0;
 for (auto& t: kek) {
  if (t.first == 0) {
   goo.add (t.second, 1);
   ++cnt;
  } else if (t.first == 1) {
   int x = goo.get (1, 1);
   cout << tmp[x] << '\n';
   goo.add (x, -1);
   --cnt;
  } else if (t.first == 2) {
   int x = goo.get (1, cnt);
   cout << tmp[x] << '\n';
   goo.add (x, -1);
   --cnt;
  } else {
   int x = goo.get (1, (cnt + 1) / 2);
   cout << tmp[x] << '\n';
   goo.add (x, -1);
   --cnt;
  }
 }





}