#include <fstream>

#define NMAX 200100

using namespace std;

ifstream fin("heapuri.in");
ofstream fout("heapuri.out");

int N, Heap[NMAX], Pos[NMAX], heapLen, A[NMAX], vecLen;

inline int Left(int i)
{
	return 2*i;
}
inline int Right(int i)
{
	return 2*i+1;
}
inline int Parent(int i)
{
	return i/2;
}
inline void Switch(int &a, int &b)
{
	a += b;
	b = a - b;
	a -= b;
}

void heapReconstruct(int i)
{
	int l = Left(i), r = Right(i), min = i;
	
	if (l <= heapLen && A[Heap[l]] < A[Heap[i]])
		min = l;
	
	if (r <= heapLen && A[Heap[r]] < A[Heap[min]])
		min = r;
	
	if (min != i)
	{
		Switch(Heap[i], Heap[min]);
		Switch(Pos[Heap[i]], Pos[Heap[min]]);
		heapReconstruct(min);	
	}
}

void heapUpdate(int i)
{
	while (i > 0 && A[Heap[i]] < A[Heap[i/2]])
	{
		Switch(Heap[i], Heap[i/2]);
		Switch(Pos[Heap[i]], Pos[Heap[i/2]]);
		i /= 2;
	}
}

int main()
{
	int iType, i, x;
	
	fin >>N;
	
	for (i = 1; i <= N; i++)
	{
		fin >>iType;
		
		if (iType == 1)
		{
			vecLen++;
			fin >>A[vecLen];
			heapLen++;
			Pos[vecLen] = heapLen;
			Heap[heapLen] = vecLen;
			heapUpdate(heapLen);
		}
		if (iType == 2)
		{
			fin >>x;

			Pos[Heap[heapLen]] = Pos[x];
			Heap[Pos[x]] = Heap[heapLen];
						
			heapLen--;
			
			heapReconstruct(Pos[x]);
			
		}
		if (iType == 3)
		{
			fout <<A[Heap[1]]<<'\n';
		}		
	}
	
	
	fout.close();
	return 0;
}