stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<string>

using namespace std;



int main()

{

	string op;

	int num;

	priority_queue<int>pq;

	while (cin >> op)

	{

		if (op == "end") break;

		if (op == "insert")

		{

			cin >> num;

			pq.push(num);

		}

		else if (op == "extract")

		{

			cout << pq.top() << endl;

			pq.pop();

		}

	}

}

// Faster C++ solution for the same problem (measured speedup: 5.237022319310901x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace  std;

const int N=2e6+5;

#define INFTY (1<<30)

int h,a[N];

void maxheapify(int i){

    int l,r,largest;

    l=2*i;

    r=2*i+1;

    if(l<=h&&a[l]>a[i]) largest=l;

    else largest=i;

    if(r<=h&&a[r]>a[largest]) largest=r;

    if(largest!=i){

        swap(a[i],a[largest]);

        maxheapify(largest);

    }

}

int extract(){

    int maxv;

    if(h<1) return -INFTY;

    maxv=a[1];

    a[1]=a[h--];

    maxheapify(1);

    return maxv;

}

void increasekey(int i,int key){

    if(key<a[i]) return;

    a[i]=key;

    while(i>1&&a[i/2]<a[i]){

        swap(a[i],a[i/2]);

        i/=2;

    }

}

void insert(int key){

    h++;

    a[h]=-INFTY;

    increasekey(h, key);

}

int main(){

    int key;

    char com[10];

    while(1){

        scanf("%s",com);

        if(com[0]=='e'&&com[1]=='n') break;

        if(com[0]=='i'){

            scanf("%d",&key);

            insert(key);

        }

        else

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

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.140646255635576x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

using namespace std;



#define par(x) ((x)>>(1))

#define lc(x) ((x)<<(1))

#define rc(x) ((x)<<(1)|1)



const int MAX = 2000010;

int heap[MAX];

int len;

char cmd[10];



void shiftUp(int p) {

    int parent = par(p);

    if (parent>=1 && heap[parent]<heap[p]) {

        swap(heap[parent], heap[p]);

        shiftUp(parent);

    }

}



void shiftDown(int p) {

    int l = lc(p);

    int r = rc(p);

    int largest = p;

    if (l <= len && heap[l] > heap[p]) {

        largest = l;

    }

    if (r <= len && heap[r] > heap[largest]) {

        largest = r;

    }

    if (largest != p) {

        swap(heap[largest], heap[p]);

        shiftDown(largest);

    }

}



void insert(int x) {

    heap[++len] = x;

    shiftUp(len);

}



int pop() {

    int x = heap[1];

    swap(heap[1], heap[len]);

    len--;

    if (len > 0) {

        shiftDown(1);

    }

    return x;

}



int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    len = 0;

    while (~scanf("%s", cmd)) {

        if (strcmp(cmd, "insert") == 0) {

            int num = 0;

            scanf("%d", &num);

            insert(num);

        } else if (strcmp(cmd, "extract") == 0) {

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

        } else if (strcmp(cmd, "end") == 0) {

            break;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.141002686939336x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}
// Slower C++ solution:
#if debug

#include<iostream>



using namespace std;

int H=0;

int A[2000000+2];



void maxHeapify(int i){

	int l=2*i;

	int r=2*i+1;

	int largest;

	if(l<=H&&A[l]>A[i]){

		largest=l;

	}

	else

		largest=i;

	if(r<=H&&A[r]>A[i])

			largest=i;

	if(largest!=i){

		swap(A[largest],A[i]);

		maxHeapify(largest);

	}

}



int extract(){

	int maxv;

	if(H<1) return -1e9;

	maxv=A[1];

	A[1]=A[H--];

	maxHeapify(1);

	return maxv;

}



void increaseKey(int i,int key){

	if(key<A[i]) return;

	A[i]=key;

	while(i>1&&A[i/2]<A[i]){

		swap(A[i/2],A[i]);

		i/=2;

	}

}



void insert(int key){

	H++;

	A[H]=-1e9;

	increaseKey(H,key);	

}

#include<string>

int main(){

	int key;

	string s;

	while(cin>>s){

		if(s=="insert"){

			cin>>key;

			insert(key);

		}

		else if(s=="extract"){

			cout<<extract()<<endl;

		}

		else 

			break;

	}

	return 0;

}

#endif



#include<iostream>

#include<queue>

using namespace std;



int main(){

	char s[20];

	priority_queue<int> que;

	while(1){

		cin>>s;

		if(s[0]=='e'&&s[1]=='n') break;

		if(s[0]=='i'){

			int key;

			cin>>key;

			que.push(key);

		}

		else if(s[0]=='e'){

			cout<<que.top()<<endl;

			que.pop();

		}

	}

}

// Faster C++ solution for the same problem (measured speedup: 5.225603391105471x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=2*1e6+5;

#define INF (1<<30)

int H,a[maxn];



void maxHeapify(int i)

{

    int l,r,tmp;

    l=i*2,r=l+1;

    if(l<=H&&a[l]>a[i]) tmp=l;

    else tmp=i;

    if(r<=H&&a[r]>a[tmp]) tmp=r;

    if(tmp!=i){

        swap(a[tmp],a[i]);

        maxHeapify(tmp);

    }

}



int extract()

{

    int maxv;

    if(H<1) return -INF;

    maxv=a[1];

    a[1]=a[H--];

    maxHeapify(1);

    return maxv;

}

void increaseKey(int i,int key)

{

    if(key<a[i]) return;

    a[i]=key;

    while(i>1&&a[i/2]<a[i]){

        swap(a[i],a[i/2]);

        i=i/2;

    }

}



void insert(int key)

{

    H++;

    a[H]=-INF;

    increaseKey(H,key);

}



int main()

{

    H=0;

    int key;

    char com[10];

    while(1){

        scanf("%s",com);

        if(com[0]=='e'&&com[1]=='n') break;

        if(com[0]=='i'){

            cin>>key;

            insert(key);

        }else{

            cout<<extract()<<endl;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.178874739606347x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include<queue>

#include<cstdio>

using namespace std;

int main()

{

    int key;

    char s[1001];

    priority_queue<int>PQ;

    while(1){

            scanf("%s",s);

        if(s[0]=='i'){

            scanf("%d\n",&key);

            PQ.push(key);

        }else if(s[0]=='e'&&s[1]=='x'){

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

            PQ.pop();

        }else{

        break;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.150507305516389x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 2000000

#define infly 1<<30

using namespace std;



int a[maxn+5],h;

char s[100];



void maxheapfy(int i)

{

    int l=i*2;

    int r=i*2+1;

    int large;

    if(l<=h && a[l]>a[i])

        large=l;

    else large=i;

    if(r<=h && a[r]>a[large])

        large=r;



    if(large!=i)

    {

         swap(a[i],a[large]);

         maxheapfy(large);

    }



}



void heapinsert(int i,int k)

{

    if(k<a[i]) return;

    a[i]=k;

    while(i>1 && a[i/2]<a[i])

    {

        swap(a[i],a[i/2]);

        i/=2;

    }

}



void insert(int k)

{

    a[++h]=-infly;

    heapinsert(h,k);

}



int extract()

{

    if(h<1) return -infly;

    int maxv=a[1];

    swap(a[h],a[1]);

    h--;

    maxheapfy(1);

    return maxv;

}



int main()

{

    int k;

    while(scanf("%s",s) && s[2]!='d')

    {

        if(s[0]=='i')

        {

            scanf("%d",&k);

            insert(k);

        }

        else if(s[0]=='e')

        {

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

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.101494998090104x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 2000000

#define infly 1<<30

using namespace std;



int a[maxn+5],h;

char s[100];



void maxheapfy(int i)

{

    int l=i*2;

    int r=i*2+1;

    int large;

    if(l<=h && a[l]>a[i])

        large=l;

    else large=i;

    if(r<=h && a[r]>a[large])

        large=r;



    if(large!=i)

    {

         swap(a[i],a[large]);

         maxheapfy(large);

    }



}



void heapinsert(int i,int k)

{

    if(k<a[i]) return;

    a[i]=k;

    while(i>1 && a[i/2]<a[i])

    {

        swap(a[i],a[i/2]);

        i/=2;

    }

}



void insert(int k)

{

    a[++h]=-infly;

    heapinsert(h,k);

}



int extract()

{

    int maxv=a[1];

    swap(a[h],a[1]);

    h--;

    maxheapfy(1);

    return maxv;

}



int main()

{

    int k;

    while(scanf("%s",s) && s[2]!='d')

    {

        if(s[0]=='i')

        {

            scanf("%d",&k);

            insert(k);

        }

        else if(s[0]=='e')

        {

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

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.099568605327734x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main() {

	ios_base::sync_with_stdio(0);

	

	priority_queue<ll> pq;

	string s;

	

	while(cin>>s && s!="end")

	{ 

		 ll x;



		if(s=="insert") 

		{		 cin>>x;

			

			pq.push(x);

	

			

		}

		else {

			x=pq.top();

			pq.pop();

			printf("%lld\n",x);

		}

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.283086976513377x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

int main(){

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    string s;

    int num;

    priority_queue<int> pq;

    while(cin>>s){

        if(s=="insert"){

            cin>>num;

            pq.push(num);

        }

        else if(s=="extract"){

            cout<<pq.top()<<'\n';

            pq.pop();

        }

        else{

            while(!pq.empty())

                pq.pop();

        }

    }

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.2910490427479x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <algorithm>

#include <queue>

using namespace std;



int main()

{

    priority_queue<int> q;

    char op[20];

    int k;

    while (scanf("%s", op) != EOF&&op[2] != 'd') {

        if (op[0] == 'i') {

            scanf("%d", &k);

            q.push(k);

        }

        else {

            int k = q.top();

            q.pop();

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

        }

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.149067015683598x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



#define ms(a,x) memset(a,x,sizeof(a))

using namespace std;



#define N 200

#define MAX 2000000



typedef long long ll;



int main(){

	char com[20];

	priority_queue<int>PQ;

	

	while(1){

		scanf("%s",com);

		if(com[0]=='i'){

			int key;

			scanf("%d",&key);

			PQ.push(key);

		}

		else if(com[1]=='x'){

			cout<<PQ.top()<<endl;

			PQ.pop();

		}

		else if(com[0]=='e'){

			break;

		}

	}

	return 0;

}






// Faster C++ solution for the same problem (measured speedup: 5.173082378436764x):
#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define N 2000005

#define INF 2000000010

int n = 0;

int a[N];

void swap(int *a, int *b){

    int t;

    t = *a;

    *a= *b;

    *b = t;

}

void maxHeapify(int i){

    int l = 2*i;

    int r = 2*i+1;

    int maxi = i;

    if(l <= n && a[l] > a[maxi]){

        maxi = l;

    }

    if(r <= n && a[r] > a[maxi]){

        maxi = r;

    }

    if(maxi != i){

        swap(&a[i], &a[maxi]);

        maxHeapify(maxi);

    }

}

void insert(int key){

    a[++n] = key;

    int temp = n;

    while(temp > 1 && a[temp/2] < key){

        swap(&a[temp], &a[temp/2]);

        temp /= 2;

    }

}

int extract(){

    if(n < 1) return 0;

    int res = a[1];

    a[1] = a[n--];

    maxHeapify(1);

    return res;

}

int main(){

    char s[10];

    int k;

    while(scanf("%s", s), strcmp(s, "end")){

        if(s[0] == 'i'){

            scanf("%d", &k);

            insert(k);

        }else if(s[0] == 'e'){

            int p = extract();

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

        }

    }

    return 0;

}