#!/usr/bin/env.python
# -*- coding:utf-8 -*-
'''
本题关键在于PeekMedian操作，若每次都对堆栈的镜像进行排序，则必定超时。
故用树状数组来加速查询。
树状数组最初时为了解决这么一个问题，有一个数组，对每个位置，想获得其累计和。
若数组存原始数字，则查询(求和)需要O(n)时间复杂度，更新需要O(1)
若每个位置存累计和，则可以以O(1)获得每个位置的值(减去前一位的)和累计和，但是若有数据更新，则后面的都要更新，为O(n)
树状数组是为了兼顾两种操作，使得时间复杂度都为O(log n)
将原始数组从1号位开始划分，每一段都为2格，第0位单独。如图 'https://blog.csdn.net/jiayizhenzhenyijia/article/details/80066292'
可见，其中奇数下标用普通数组的值，2的幂下标用累积数组的值，其余偶数下标的值按2的幂次的跨度累积求和。

对于x的二进制表示，如x = 010111000，需要得到最低位1所表示的数，即1000。
计算机中负数是通过补码来表示的。负数的补码=反码+1，负数的反码=负数原码符号位不变，后面依次取反
010111000对应的负数原码为110111000，其补码 = 101000111+1 = 101001000，x&(-x)，按位与，都为1才是1，可以得到1000
此种取最末尾1开始的串的操作通常定义为函数lowbit(x)。则对任意二进制数，可以通过lowbit(x)拆分成多个开头为1后面全0的小串相加
如 1111 = 1000 + 100 + 10 + 1。这些小串对应的十进制数正好是2的等比数列。以此数列为区间端点，正好对应了树状数组中每一个大区间。
去尾：1111 去尾得 1110 去尾得1100，即去尾操作为x -= lowbit(X)， 去尾操作还可以更快地写为 x = x&(x-1)

二进制是辅助理解树状数组的神器，对应到树状数组：
由树状数组定义，c(8) = c[4]+c[6]+c[7]+a[8], c[7] = a[7]....
若要统计前8个的总和，因为8是2^3，按照树状数组的定义，直接从数组c中获得getSum(8)=c[8]
从二进制角度来看，8的二进制为1000，去尾为0，故可以直接得到getsum(8) = c[8]
7的二进制为111，连续去尾得到非零序列，110，100，对应十进制数6，4，而getsum(7) = c[7]+c[6]+c[4]
可以发现，想要得到前i个数的和，只需对下标i的二进制数不断去尾，从树状数组C中取小区间和累加即可
从而把求和过程与去尾过程相关联。
若要更新，则只要把树状数组里路径上的点更新即可。如a[3]发生改动，则c[3],c[4],c[8],c[16]...一系列都要改动。那么这些下标有啥规律呢。
3：11，4：100，8：1000，16：10000，可以看到为前面增加一位1，后面全变成0，即递推规律为下标x += lowbit(x)
从后去尾和从前更新的时间复杂度都为O(log n)，分别对应查询累计和和更新树状数组的操作。
------------------------------------------------------------------------------------------------------------------------------
本题题意要找栈中的元素大小的中位数。
不同于查最大最小值，极值可以记录，压栈时出现更厉害的，要更新也方便，当极值被弹出更新稍微麻烦点，需要找次极值，但也只要从被弹出值往对面极值扫描即可（可能有冗余值，所以本身那个值还得确认有没有），可以用一个字典维护每个元素得个数，扫描过程中，发现某个次极值个数不为0，那他就是新的极值。
对于查中值，如果每次都排序再查，则不仅要同步维护一个镜像，且每次排序耗时长。考虑用树状数组。

首先，先看两个数组。简化考虑，都是正整数。
普通数组A，下标记录对应元素在栈中的个数。则压栈和出栈对应的数组A更新非常方便。但是要求某某大小排名的数比较麻烦，需要从某一端开始去统计个数。
累计数组B，为数组A的累计版本，下标记录到此为止的累计和。即B[i] = sum(A[:i+1])，即下标i处记录栈中元素大小不超过i的元素个数。且这些元素里面最大只能是i，但不一定是i。
如栈中只有一个元素3，则数组B[3:]都是1，要得到某排名的确切的元素值，需要用上限逼近（对应升序排名，降序排名问题则转化为升序排名问题）。
此时可以用变形的二分法（相同则取尽可能小）确定上确界（由head返回）。上确界数值即为对应排名的元素。数组B虽然查询方便，但是压栈出栈导致的更新是致命的，后面的一系列累计值都得改变。

因此采用树状数组C来平衡更新与查询的开销，大小开为N。本题都是正整数，所以不考虑0位。若有0或者负数，则向右平移转化为正整数即可，取到值后扣掉平移量。
当发生更新时，如插入某个数x，则只需更新树状数组中与x关联的下标位即可。这些下标通过反复 x += lowbit(x)即可获得。如插入一个7，则7，8，16，32。。。下去都要更新(个数+1)。通过lowbit的方式不断向前进行端点推进。每个到达端点都是2的次方数。弹出元素同理，个数-1而已。因为是以2的指数增长的，所以更新是O(logN)的时间复杂度。
查询即求累计和的过程，若要查升序排名为k的元素。则要求上确界，同样用变形的二分法。只是此时的累计和不同于数组B的下标y直接访问，而是要通过getSum(y)函数，getSum函数的实现是对y的二进制不断去尾再取C中值来叠加。以2的指数减小。故getSum同样是O(logN)的时间复杂度。二分又是O(logN)的时间复杂度，故查询的时间复杂度是O((logN)^2)

树状数组C的构建其实和普通数组A和累计数组B没有任何关系了。可以看成一个独立的数据结构，其中按某种规律分布着普通数组A和累计数组B的某些值。如奇数位等于数组A的值，2的次方位等于数组B的值。树状数组多用于快速定位累计值所在位置，又方便更新维护。



'''
import math

N = int(input())
stack = []
maxn = 100001
c = [0] * maxn


def lowbit(x):
    return x & (-x)


def update(i, num):
    while i < maxn:
        c[i] += num
        i += lowbit(i)

def getsum(i):
    sum_ = 0
    while i >= 1:
        sum_ += c[i]
        i -= lowbit(i)
    return sum_

def PeekMedian(k):
    s, e = 1, maxn
    while s < e:
        mid = (s + e) // 2
        count = getsum(mid)
        if count >= k: # 可能有好多个i，对应getsum(i)==k的，按题意应要找到最小的
            e = mid
        else:
            s = mid + 1
    return s

for i in range(N):
    cc = input()
    if cc[1] == 'u':
        temp = int(cc.split()[1])
        stack.append(temp)
        update(temp, 1)
    elif cc[1] == 'o':
        if len(stack) > 0:
            temp = stack.pop()
            update(temp,-1)
            print(temp)
        else:
            print('Invalid')
    else:
        if len(stack) > 0:
            k = math.ceil(len(stack) / 2)
            print(PeekMedian(k))
        else:
            print('Invalid')
