//二叉堆
#include <cstdio>
#include <iostream>
using namespace std;
int read()
{
int num1=0,fu=1;
char ch=getchar();
if(ch=='-')fu=-1;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')
{
num1=num1*10+ch-'0';
ch=getchar();
}
return num1*fu;
}
int a[100004]={0};//堆
int n;
void put(int);
void get(int);
int min1(int ,int);
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
put(i);
}
int m=read();//修改次数
for(int i=1;i<=m;i++)
{
bool bo=read();// bo=1时添加新元素，bo=0时输出并删除最小元素
if(bo)
{
int num=read();
a[n++]=num;
put(n);
}
else
{
printf("%d\n",a[1]);
a[1]=a[n--];
get(1);
}
}
return 0;
}
void put(int i)
{
if(a[i]>=a[i/2])return;//已包括i=1
else
{
swap(a[i],a[i/2]);
put(i/2);
}
}
void get(int i)
{
if(i*2>n)return;
else
{
int t=min1(i*2,i*2+1);
if(a[i]<=a[t])return;
else
{
swap(a[i],a[t]);
get(t);
}
}
}
int min1(int z,int x)
{
if(x>n)return z;
else
{
return a[z]<a[x]?z:x;
}
}
