//#include<bits/stdc++>

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<stdlib.h>

 #include<queue>

 #include<map>

 #include<stack>

 #include<set>

 #define LL long long

 #define ull unsigned long long

 #define inf 0x7f7f7f7f 

 using namespace std;

 const int maxn = 1e5 + ;

 int n, size;

 int sum[maxn];

 stack<int>sss;

 int small = , big = 1e5;

 void add(int x, int val)

 {

     while(x < 1e5){

         sum[x] += val;

         x += (x & -x);

     }

 } 

 int query(int x)

 {

     int ans = ;

     while(x){

         ans += sum[x];

         x -= (x & -x);

     }

     return ans;

 }

 int main()

 {

     scanf("%d", &n);

     while(n--){

         string op;

         cin>>op;

         if(op == "Push"){

             int key;

             cin>>key;

             sss.push(key);

             //small = min(small, key);

             //big = max(big, key);

             add(key, );

         }

         else if(op == "Pop"){

             if(sss.size() == ){

                 printf("Invalid\n");

             }

             else{

                 add(sss.top(), -);

                 printf("%d\n", sss.top());

                 sss.pop();

             }

         }

         else if(op == "PeekMedian"){

             if(sss.size() == ){

                 printf("Invalid\n");

             }

             else{

                 int st = small, ed = big;

                 int ans = ;

                 while(st <= ed){

                     int mid = (st + ed) / ;

                     size = sss.size();

                     int res = query(mid);

                     if(res < (size + ) / ){

                         st = mid + ;

                     }

                     else{

                         ans = mid;

                         ed = mid - ;

                     }

                 }

                 printf("%d\n", ans);

             }

         }

     }

     return ;

 }