Monocarp and Polycarp are working as waiters in Berpizza, a pizzeria located near the center of Bertown. Since they are waiters, their job is to serve the customers, but they choose whom they serve first differently.

At the start of the working day, there are no customers at the Berpizza. They come there one by one. When a customer comes into the pizzeria, she sits and waits for Monocarp or Polycarp to serve her. Monocarp has been working in Berpizza for just two weeks, so whenever he serves a customer, he simply chooses the one who came to Berpizza first, and serves that customer.

On the other hand, Polycarp is an experienced waiter at Berpizza, and he knows which customers are going to spend a lot of money at the pizzeria (and which aren't) as soon as he sees them. For each customer, Polycarp estimates the amount of money this customer can spend, and when he serves a customer, he chooses the one that is expected to leave the most money at Berpizza (in case there are several such customers, he chooses the one who came first among them).

Obviously, no customer can be served twice, so Monocarp and Polycarp choose which customer to serve only among those who haven't been served yet.

When the number of customers gets really high, it becomes difficult for both Monocarp and Polycarp to choose the customer they are going to serve. Your task is to write a program that makes these choices for them. Formally, your program should be able to process three types of queries:

$1$ $m$ — a customer comes to Berpizza, and Polycarp estimates the amount of money that they will spend as $m$;

$2$ — Monocarp serves a customer which came to the pizzeria first;

$3$ — Polycarp serves a customer which is expected to spend the largest amount of money at the pizzeria (if there are several such customers, the one that came to the pizzeria first is chosen).

For each query of types $2$ and $3$, report the number of the customer who was served (the customers are numbered in the order they come to the pizzeria, starting from $1$).


-----Input-----

The first line contains one integer $q$ ($2 \le q \le 5 \cdot 10^5$) — the number of queries.

Then $q$ lines follow, each describing a query in one of the following formats:

$1$ $m$ ($1 \le m \le 5 \cdot 10^5$) — a customer comes to Berpizza, and Polycarp estimates the amount of money that they will spend as $m$;

$2$ — Monocarp serves a customer which came to the pizzeria first;

$3$ — Polycarp serves a customer which is expected to spend the largest amount of money at the pizzeria (if there are multiple such customers, the one that came to the pizzeria first is chosen).

Queries of type $2$ and $3$ are asked only when there exists at least one customer that hasn't been served yet. There is at least one query of type $2$ or $3$ in the input.


-----Output-----

For each query of type $2$ or $3$, print one integer — the number of the customer that has been served in that event. The customers are numbered in the order in which they come to the pizzeria, starting from $1$.


-----Examples-----

Input
8
1 8
1 10
1 6
3
2
1 9
2
3
Output
2 1 3 4
Input
6
1 8
1 10
1 8
3
3
3
Output
2 1 3
Input
8
1 103913
3
1 103913
1 103913
3
1 103913
1 103913
2
Output
1 2 3


-----Note-----

None

Difficulty: MEDIUM
Tags: Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
import heapq

def solution(n: int, arr: [[int]]) -> [int]:
	queue = []
	heap = []
	result = []
	lastIndex = 0
	for i in arr:
		if i[0] == 1:
			lastIndex += 1
			element = [-i[1], lastIndex, False]
			queue.append(element)
			heapq.heappush(heap, element)
		if i[0] == 2:
			customer = queue.pop(0)
			while customer[2] == True:
				customer = queue.pop(0)
			customer[2] = True
			result.append(customer[1])
		if i[0] == 3:
			customer = heapq.heappop(heap)
			while customer[2] == True:
				customer = heapq.heappop(heap)
			customer[2] = True
			result.append(customer[1])
	return result

def main():
	n = int(input())
	arr = [[int(j) for j in input().split(' ')] for i in range(n)]
	print(' '.join([str(i) for i in solution(n, arr)]))
main()


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
dq = deque([])
pq = []
heapify(pq)
i = 0
md = {}
for _ in range(int(inp())):
	k = lmp()
	if k[0] == 1:
		heappush(pq, (-k[1], i))
		dq.appendleft(i)
		md[i] = 1
		i += 1
	elif k[0] == 2:
		aa = dq.pop()
		while md[aa] == -1:
			aa = dq.pop()
		print(aa + 1, end=' ')
		md[aa] = -1
	else:
		aa = heappop(pq)
		while md[aa[1]] == -1:
			aa = heappop(pq)
		print(aa[1] + 1, end=' ')
		md[aa[1]] = -1


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import combinations, permutations
from bisect import *
from fractions import Fraction
from heapq import *
from random import randint

class Data:

	def __init__(self, num, value):
		self.num = num
		self.value = value

	def __lt__(self, other):
		if self.value != other.value:
			return self.value > other.value
		else:
			return self.num < other.num

def main():
	a = []
	b = deque()
	heapify(a)
	c = set()
	d = 1
	for _ in range(int(input())):
		x = input().rstrip()
		if len(x) == 1:
			if x == '3':
				z = heappop(a)
				while z.num in c:
					z = heappop(a)
				print(z.num, end=' ')
				c.add(z.num)
			else:
				z = b.popleft()
				while z in c:
					z = b.popleft()
				print(z, end=' ')
				c.add(z)
		else:
			x = list(map(int, x.split()))
			heappush(a, Data(d, x[1]))
			b.append(d)
			d += 1
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


ll = []
m = 0
k = 1
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
from queue import Queue, PriorityQueue
q = PriorityQueue()
co = 1
que = Queue()
done = set()
for _ in range(int(input())):
	l = list(map(int, input().split()))
	if len(l) > 1:
		que.put(co)
		p = 10 ** 9 - l[1]
		q.put((p, co))
		co += 1
	elif l[0] == 2:
		first = que.get()
		while first in done:
			first = que.get()
		print(first, end=' ')
		done.add(first)
	else:
		first = q.get()
		while first[1] in done:
			first = q.get()
		print(first[1], end=' ')
		done.add(first[1])


import os
import sys
import math
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def dijkstra(start, distance, path, n):
	visited = [False for _ in range(n)]
	distance[start] = 0
	for i in range(n):
		v = -1
		for j in range(n):
			if not visited[v] and (v == -1 or distance[j] < distance[v]):
				v = j
		if distance[v] == math.inf:
			break
		visited[v] = True
		for edge in adj[v]:
			destination = edge[0]
			weight = edge[1]
			if distance[v] + weight < distance[destination]:
				distance[destination] = distance[v] + weight
				path[destination] = v

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def ncr(n, r):
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def npr(n, r):
	return math.factorial(n) // math.factorial(n - r)

def seive(n):
	primes = [True] * (n + 1)
	ans = []
	for i in range(2, n):
		if not primes[i]:
			continue
		j = 2 * i
		while j <= n:
			primes[j] = False
			j += i
	for p in range(2, n + 1):
		if primes[p]:
			ans += [p]
	return ans

def factors(n):
	factors = []
	x = 1
	while x * x <= n:
		if n % x == 0:
			if n // x == x:
				factors.append(x)
			else:
				factors.append(x)
				factors.append(n // x)
		x += 1
	return factors
from heapq import *

def main():
	try:
		time = []
		ti = 0
		money = []
		heapify(money)
		q = inp()
		lst = [0] * (q + 1)
		cou = 1
		for i in range(q):
			a = input()
			if a[0] == '1':
				a = int(a.split()[1])
				time.append((cou, a))
				heappush(money, (-a, cou))
				cou += 1
			elif a[0] == '2':
				while ti != len(time) and lst[time[ti][0]]:
					ti += 1
				lst[time[ti][0]] = 1
				print(time[ti][0], end=' ')
				ti += 1
			else:
				x = heappop(money)
				while lst[x[1]] and len(money):
					x = heappop(money)
				lst[x[1]] = 1
				print(x[1], end=' ')
	except Exception as e:
		print(e)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys, functools, collections, bisect, math, heapq
input = sys.stdin.readline
print = sys.stdout.write
sys.setrecursionlimit(200000)
mod = 10 ** 9 + 7
lpq = []
stack = collections.deque()
served = set()
curr = 1
t = int(input())
for _ in range(t):
	q = list(map(int, input().strip().split()))
	if len(q) == 2:
		stack.append((curr, q[1]))
		heapq.heappush(lpq, (-q[1], curr))
		curr += 1
	elif q[0] == 2:
		while True:
			(x, y) = stack.popleft()
			if x not in served:
				print(str(x) + ' ')
				served.add(x)
				break
	else:
		while True:
			(x, y) = heapq.heappop(lpq)
			if y not in served:
				print(str(y) + ' ')
				served.add(y)
				break


import math
import heapq
IP = lambda : list(map(int, input().split()))
lst = []
i = j = 1
served = [0] * (5 * 10 ** 5 + 1)
res = []
heapq.heapify(lst)
for _ in range(int(input())):
	tmp = IP()
	if tmp[0] == 1:
		heapq.heappush(lst, (-tmp[1], i))
		i += 1
	elif tmp[0] == 2:
		while served[j] == 1:
			j += 1
		served[j] = 1
		res.append(j)
	elif tmp[0] == 3:
		per = heapq.heappop(lst)
		while served[per[1]]:
			per = heapq.heappop(lst)
		served[per[1]] = 1
		res.append(per[1])
print(' '.join(map(str, res)))


import heapq
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))
currSmallest = 1
servedCustomers = set()
maxHeap = []
currCust = 1
ans = []
q = int(input())
for _ in range(q):
	in_ = [int(x) for x in input().split()]
	if len(in_) == 1:
		if in_[0] == 2:
			while currSmallest in servedCustomers:
				currSmallest += 1
			ans.append(currSmallest)
			servedCustomers.add(currSmallest)
		else:
			while True:
				(negMoney, cust) = heapq.heappop(maxHeap)
				if cust not in servedCustomers:
					break
			ans.append(cust)
			servedCustomers.add(cust)
	else:
		moneyEstimate = in_[1]
		heapq.heappush(maxHeap, [-moneyEstimate, currCust])
		currCust += 1
oneLineArrayPrint(ans)


from heapq import heappop, heappush
import sys
input = sys.stdin.readline
perc = 0
served = {}
pera = []
curs = 1
ans = []
for _ in range(int(input())):
	inp = input().split()
	if inp[0] == '1':
		m = int(inp[1])
		perc += 1
		heappush(pera, (-m, perc))
		served[perc] = False
	else:
		q = int(inp[0])
		if q == 2:
			while served[curs]:
				curs += 1
			served[curs] = True
			ans.append(curs)
		else:
			while served[pera[0][1]]:
				heappop(pera)
			(_, i) = heappop(pera)
			ans.append(i)
			served[i] = True
print(*ans)


import math
import heapq

def S():
	return input()

def M():
	return map(int, input().split())

def I():
	return int(S())

def L():
	return list(M())
q = I()
a = []
di = {}
m = 10000000
k = 1
t = 1
ar = []
heapq.heapify(a)
for i in range(q):
	l = L()
	if len(l) == 2:
		heapq.heappush(a, (m - l[1], l[1], k))
		di[k] = 0
		k += 1
	elif l[0] == 2:
		while di.get(t, 0) == 1:
			t += 1
		ar.append(t)
		di[t] = 1
		t += 1
	else:
		p = heapq.heappop(a)
		while di.get(p[2]) == 1:
			p = heapq.heappop(a)
		di[p[2]] = 1
		ar.append(p[2])
print(*ar)


import os, sys
from io import BytesIO, IOBase
from heapq import *

def main():
	time = []
	ti = 0
	money = []
	heapify(money)
	q = int(input())
	lst = [0] * (q + 1)
	cou = 1
	for i in range(q):
		a = input()
		if a[0] == '1':
			a = int(a.split()[1])
			time.append((cou, a))
			heappush(money, (-a, cou))
			cou += 1
		elif a[0] == '2':
			while ti != len(time) and lst[time[ti][0]]:
				ti += 1
			lst[time[ti][0]] = 1
			print(time[ti][0], end=' ')
			ti += 1
		else:
			x = heappop(money)
			while lst[x[1]] and len(money):
				x = heappop(money)
			lst[x[1]] = 1
			print(x[1], end=' ')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import heapq
mono = []
poly = []
d = {}
count = 1
ans = []
q = int(input())
for i in range(q):
	query = list(input().split())
	if len(query) > 1:
		heapq.heappush(mono, [count, int(query[1])])
		heapq.heappush(poly, [-int(query[1]), count])
		count += 1
	elif query[0] == '2':
		while 1:
			p = heapq.heappop(mono)
			try:
				del d[p[0]]
			except:
				ans.append(p[0])
				d[p[0]] = 1
				break
	elif query[0] == '3':
		while 1:
			p = heapq.heappop(poly)
			try:
				del d[p[1]]
			except:
				ans.append(p[1])
				d[p[1]] = 1
				break
print(*ans)


from sys import stdin, stdout
from heapq import heappop, heappush

def main():
	(ans, visited, hp) = ([], [], [])
	start = 0
	for _ in range(int(stdin.readline())):
		q = stdin.readline()
		if q[0] == '1':
			(_, v) = map(int, q.split())
			visited.append(0)
			heappush(hp, (-1 * v, len(visited) - 1))
		elif q[0] == '2':
			while visited[start] == 1:
				start += 1
			ans.append(start + 1)
			visited[start] = 1
		else:
			while visited[hp[0][1]] == 1:
				heappop(hp)
			(_, ind) = heappop(hp)
			ans.append(ind + 1)
			visited[ind] = 1
	for v in ans:
		stdout.write('%d ' % v)
	stdout.write('\n')
main()


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	n = int(inp())
	h = []
	val = []
	que = deque([])
	ans = []
	for i in range(n):
		a = lis()
		if a[0] == 1:
			ind = len(val)
			heappush(h, (-a[1], ind))
			val.append(a[1])
			que.append(ind)
		if a[0] == 2:
			while val[que[0]] == -1:
				que.popleft()
			temp = que.popleft()
			ans.append(temp + 1)
			val[temp] = -1
		if a[0] == 3:
			temp = heappop(h)
			while val[temp[1]] == -1:
				temp = heappop(h)
			ans.append(temp[1] + 1)
			val[temp[1]] = -1
	print(' '.join((str(ans[i]) for i in range(len(ans)))))
testcase(1)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def S():
	return input().strip()

def print_list(l):
	print(' '.join(map(str, l)))
from heapq import *
from collections import deque as dq
u = set()
q = dq()
heap = []
now = 1
for _ in range(N()):
	s = RLL()
	if s[0] == 1:
		heappush(heap, (-s[1], now))
		q.append(now)
		now += 1
	elif s[0] == 2:
		p = q.popleft()
		while p in u:
			p = q.popleft()
		print(p, end=' ')
		u.add(p)
	else:
		(_, p) = heappop(heap)
		while p in u:
			(_, p) = heappop(heap)
		print(p, end=' ')
		u.add(p)


import heapq
served = []
cur = 0
pq = []
q = int(input())
for _ in range(q):
	query = list(map(int, input().split()))
	if query[0] == 1:
		heapq.heappush(pq, (-query[1], len(served)))
		served.append(False)
	elif query[0] == 2:
		while served[cur]:
			cur += 1
		served[cur] = True
		print(cur + 1, end=' ')
	else:
		while True:
			(_, index) = heapq.heappop(pq)
			if not served[index]:
				break
		served[index] = True
		print(index + 1, end=' ')
print()


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=10 ** 10, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
from heapq import heapify, heappush, heappop
heap = []
heapify(heap)
n = int(input())
a = []
s = set()
r = []
ct = 1
ind = 0
for i in range(n):
	a1 = list(map(int, input().split()))
	if a1[0] == 1:
		num = a1[1]
		a.append(num)
		heappush(heap, (-num, ct))
		ct += 1
	elif a1[0] == 2:
		while ind < len(a) and ind + 1 in s:
			ind += 1
		s.add(ind + 1)
		r.append(ind + 1)
	else:
		(num, j) = heappop(heap)
		while j in s:
			(num, j) = heappop(heap)
		s.add(j)
		r.append(j)
print(*r)


import heapq
q = int(input())
b = []
for a in range(q):
	b.append([int(x) for x in input().split()])
klanten = []
heapq.heapify(klanten)
weg = []
res = []
tel = 1
i = 0
for a in range(q):
	if len(b[a]) == 2:
		heapq.heappush(klanten, (-b[a][1], tel))
		weg.append(False)
		tel += 1
	if b[a][0] == 2:
		while weg[i]:
			i += 1
		weg[i] = True
		res.append(str(i + 1))
	if b[a][0] == 3:
		stop = True
		while stop:
			item = heapq.heappop(klanten)
			if weg[item[1] - 1] == False:
				res.append(str(item[1]))
				weg[item[1] - 1] = True
				stop = False
print(' '.join(res))


import re
import sys
exit = sys.exit
from bisect import bisect_left as bsl, bisect_right as bsr
from collections import Counter, defaultdict as ddict, deque
from functools import lru_cache
cache = lru_cache(None)
from heapq import *
from itertools import *
from math import inf
from pprint import pprint as pp
enum = enumerate
ri = lambda : int(rln())
ris = lambda : list(map(int, rfs()))
rln = sys.stdin.readline
rl = lambda : rln().rstrip('\n')
rfs = lambda : rln().split()
d4 = [(0, -1), (1, 0), (0, 1), (-1, 0)]
d8 = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
q = ri()
(mono, poly) = ([], [])
i = 0
served = set()
for _ in range(q):
	(op, m, *_) = ris() + [0]
	if op == 1:
		i += 1
		heappush(mono, (i, i))
		heappush(poly, (-m, i))
	else:
		hp = {2: mono, 3: poly}[op]
		while 1:
			(_, j) = heappop(hp)
			if j not in served:
				break
			served.discard(j)
		print(j)
		served.add(j)


from heapq import heapify, heappop, heappush
from collections import defaultdict
coun = 0
minheap = []
maxheap = []
ans = []
dic = defaultdict(int)
try:
	for _ in range(int(input())):
		a = list(map(int, input().split()))
		if a[0] == 1:
			coun += 1
			dic[coun] = 0
			heappush(maxheap, (-a[1], coun))
			heappush(minheap, (coun, a[1]))
		elif a[0] == 2:
			(x, y) = heappop(minheap)
			while dic[x] == 1:
				(x, y) = heappop(minheap)
			dic[x] = 1
			ans.append(x)
		else:
			(x, y) = heappop(maxheap)
			while dic[y] == 1:
				(x, y) = heappop(maxheap)
			dic[y] = 1
			ans.append(y)
	print(*ans)
except:
	print(*ans)


import sys
input = sys.stdin.readline
from sys import stdin, stdout
from collections import defaultdict, Counter, deque
M = 10 ** 9 + 7
import heapq

def main():
	n = int(input())
	vis = []
	q = deque([])
	h = []
	ind = 0
	ans = []
	for i in range(n):
		l = [int(s) for s in input().split()]
		if l[0] == 1:
			vis.append(0)
			q.append([l[1], ind])
			heapq.heappush(h, [-l[1], ind])
			ind += 1
		elif l[0] == 2:
			w = q.popleft()
			while vis[w[1]] == 1:
				w = q.popleft()
			ans.append(w[1] + 1)
			vis[w[1]] = 1
		else:
			w = heapq.heappop(h)
			while vis[w[1]] == 1:
				w = heapq.heappop(h)
			ans.append(w[1] + 1)
			vis[w[1]] = 1
	print(*ans)
main()


import sys
from queue import PriorityQueue
from queue import Queue
l = sys.stdin.readlines()
i = 0
n = int(l[i].replace('\n', ''))
i = 1
filaClientes = {}
at = 1
atendidos = ''
atAtual = 0
pQ = PriorityQueue()
Q = Queue()
jaAtendido = [False] * n
while True:
	if len(l[i].replace('\n', '').split()) == 2:
		a = l[i].replace('\n', '').split()
		a = [int(a[0]), int(a[1])]
	else:
		a = int(l[i].replace('\n', ''))
	i = i + 1
	if type(a) is list:
		filaClientes[at] = a[1]
		pQ.put((-a[1], at))
		Q.put(at)
		at += 1
	elif a == 2:
		while True:
			b = Q.get()
			if jaAtendido[b]:
				continue
			atendidos += str(b) + ' '
			jaAtendido[b] = True
			break
	elif a == 3:
		while True:
			b = pQ.get()
			if jaAtendido[b[1]]:
				continue
			atendidos += str(b[1]) + ' '
			jaAtendido[b[1]] = True
			break
	if i == len(l) or i == n + 1:
		break
print(atendidos.strip())


from sys import stdin, stdout

def insert(ID):
	heap.append(ID)
	i = len(heap) - 1
	while (i - 1) // 2 >= 0 and (score[heap[(i - 1) // 2]] < score[heap[i]] or (score[heap[(i - 1) // 2]] == score[heap[i]] and heap[i] < heap[(i - 1) // 2])):
		heap[(i - 1) // 2] += heap[i]
		heap[i] = heap[(i - 1) // 2] - heap[i]
		heap[(i - 1) // 2] -= heap[i]
		i = (i - 1) // 2

def remove():
	if len(heap) == 1:
		return heap.pop()
	else:
		heap[0] += heap[-1]
		heap[-1] = heap[0] - heap[-1]
		heap[0] -= heap[-1]
		res = heap.pop()
		(n, i) = (len(heap), 0)
		while 2 * i + 1 < n:
			maxm = 2 * i + 1
			if 2 * i + 2 < n and score[heap[2 * i + 2]] > score[heap[maxm]]:
				maxm = 2 * i + 2
			elif 2 * i + 2 < n and (score[heap[2 * i + 2]] == score[heap[maxm]] and heap[maxm] > heap[2 * i + 2]):
				maxm = 2 * i + 2
			if score[heap[i]] > score[heap[maxm]] or (score[heap[i]] == score[heap[maxm]] and heap[maxm] > heap[i]):
				break
			heap[maxm] += heap[i]
			heap[i] = heap[maxm] - heap[i]
			heap[maxm] -= heap[i]
			i = maxm
		return res
N = int(stdin.readline().strip())
score = dict()
heap = []
output = []
visited = dict()
n = 1
i = 1
for __ in range(N):
	x = [int(num) for num in stdin.readline().strip().split()]
	if x[0] == 1:
		score[n] = x[1]
		insert(n)
		n += 1
	elif x[0] == 2:
		while visited.get(i, False):
			i += 1
		visited[i] = True
		output.append(i)
		i += 1
	else:
		res = remove()
		while visited.get(res, False):
			res = remove()
		output.append(res)
		visited[res] = True
for out in output[:len(output) - 1]:
	stdout.write(f'{out} ')
stdout.write(f'{output[-1]}')


import sys, heapq
n = int(sys.stdin.readline())
idx = 0
order = 0
money = []
avail = [True] * 500001
p = []
q = [[] for _ in range(500001)]
for _ in range(n):
	temp = list(map(int, sys.stdin.readline().split()))
	if temp[0] == 1:
		heapq.heappush(money, -1 * temp[1])
		heapq.heappush(p, (order, idx))
		heapq.heappush(q[temp[1]], (order, idx))
		order += 1
		idx += 1
	elif temp[0] == 2:
		while p:
			(temp_order, temp_idx) = heapq.heappop(p)
			if avail[temp_idx]:
				avail[temp_idx] = False
				print(temp_idx + 1, end=' ')
				break
	elif money:
		find = False
		while money and (not find):
			temp_money = -1 * heapq.heappop(money)
			while q[temp_money]:
				(temp_order, temp_idx) = heapq.heappop(q[temp_money])
				if avail[temp_idx] == True:
					find = True
					avail[temp_idx] = False
					print(temp_idx + 1, end=' ')
					break


import os, sys, math
from io import BytesIO, IOBase
from collections import defaultdict, deque, OrderedDict
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(input())

def In():
	return map(int, input().split())

def ln():
	return list(map(int, input().split()))

def Sn():
	return input().strip()
BUFSIZE = 8192
from heapq import heappush, heappop

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return len(a)

def solve():
	Q = I()
	pqm = []
	pqp = []
	peps = 1
	visit = set()
	for i in range(Q):
		q = list(In())
		if q[0] == 1:
			heappush(pqm, (peps, q[1]))
			heappush(pqp, (-q[1], peps))
			peps += 1
		elif q[0] == 2:
			while len(pqm):
				t = heappop(pqm)
				if t[0] not in visit:
					print(t[0], end=' ')
					visit.add(t[0])
					break
		else:
			while len(pqp):
				t = heappop(pqp)
				if t[1] not in visit:
					print(t[1], end=' ')
					visit.add(t[1])
					break
	pass

def main():
	T = 1
	for i in range(T):
		solve()
M = 998244353
P = 1000000007

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import heapq
from collections import deque
t = int(input())
queue = deque()
pq = []
done = [False for i in range(500005)]
cnt = 0
ans = []
for i in range(t):
	a = list(map(int, input().split()))
	if a[0] == 1:
		queue.append(cnt + 1)
		heapq.heappush(pq, (-a[1], cnt + 1))
		cnt += 1
	elif a[0] == 2:
		cur = queue.popleft()
		while done[cur]:
			cur = queue.popleft()
		done[cur] = True
		ans.append(str(cur))
	else:
		cur = heapq.heappop(pq)
		while done[cur[1]]:
			cur = heapq.heappop(pq)
		done[cur[1]] = True
		ans.append(str(cur[1]))
print(' '.join(ans))


from collections import deque
import sys, heapq
input = sys.stdin.readline
(q, h) = (deque(), [])
curr = 1
v = set()
res = []
for _ in range(int(input())):
	temp = [int(x) for x in input().split()]
	if temp[0] == 1:
		q.append(curr)
		heapq.heappush(h, [-temp[1], curr])
		curr += 1
	elif temp[0] == 2:
		while q and q[0] in v:
			q.popleft()
		ans = q.popleft()
		res.append(ans)
		v.add(ans)
	else:
		while h and h[0][1] in v:
			heapq.heappop(h)
		ans = heapq.heappop(h)
		res.append(ans[1])
		v.add(ans[1])
print(*res)


def Berpizza3():
	import heapq
	t = int(input())
	hp = []
	ser = []
	h = 0
	OS = []
	if t == 0:
		print()
	else:
		for i in range(t):
			C = input().split()
			if C[0] == '1':
				heapq.heappush(hp, (-int(C[1]), len(ser)))
				ser.append(False)
			elif C[0] == '2':
				while ser[h]:
					h += 1
				ser[h] = True
				OS.append(h + 1)
			else:
				while True:
					(_, i) = heapq.heappop(hp)
					if not ser[i]:
						break
				OS.append(i + 1)
				ser[i] = True
		for x in range(len(OS)):
			print(OS[x], end=' ')
Berpizza3()


from heapq import heappop, heappush, heapify
T = int(input())
cust_served = [True]
cust_money = [-1]
curr_m = 1
N = 1
heap = []
for _ in range(T):
	l = list(map(int, input().split()))
	if l[0] == 1:
		cust_served.append(False)
		cust_money.append(l[1])
		heappush(heap, [-1 * l[1], N])
		N += 1
	elif l[0] == 2:
		for i in range(curr_m, N):
			if not cust_served[i]:
				curr_m = i
				cust_served[i] = True
				print(i, end=' ')
				break
	elif l[0] == 3:
		while 1:
			el = heappop(heap)
			if not cust_served[el[1]]:
				cust_served[el[1]] = True
				print(el[1], end=' ')
				break


from collections import deque
from heapq import *

class Customer:

	def __init__(self, cid, m):
		self.cid = cid
		self.m = m
		self.served = False

	def __lt__(self, other):
		if self.m == other.m:
			return self.cid < other.cid
		return self.m < other.m

	def __eq__(self, other):
		return self.m == other.m

	def __gt__(self, other):
		return not (self < other or self == other)

	def __repr__(self):
		return 'cid: {}, m: {}'.format(self.cid, self.m)
q = int(input())
d = deque()
h = []
next_id = 1
out = []
for case in range(q):
	query = [int(t) for t in input().split()]
	if query[0] == 1:
		m = query[1]
		customer = Customer(next_id, -m)
		next_id += 1
		d.append(customer)
		heappush(h, customer)
	else:
		if query[0] == 2:
			customer = d.popleft()
			while customer.served:
				customer = d.popleft()
		else:
			customer = heappop(h)
			while customer.served:
				customer = heappop(h)
		customer.served = True
		out.append(str(customer.cid))
print(' '.join(out))


from sys import stdin
from heapq import *
Q = int(stdin.readline())
customer_id = 1
pq = []
first = 1
ans = []
served = set()
for q in range(Q):
	args = stdin.readline().split()
	if args[0] == '1':
		heappush(pq, [-1 * int(args[1]), customer_id])
		customer_id += 1
	elif args[0] == '2':
		ans.append(first)
		served.add(first)
		while first in served:
			first += 1
	else:
		while pq[0][1] in served:
			heappop(pq)
		(price, c_id) = heappop(pq)
		ans.append(c_id)
		served.add(c_id)
		while first in served:
			first += 1
print(*ans)


from heapq import heappush, heappop
heap = []
client_number = 1
served = [True]
last_served = 1
for i in range(int(input())):
	q = input().split()
	if q[0] == '3':
		while served[heap[0][1]]:
			heappop(heap)
		(_, i) = heappop(heap)
		print(i, end=' ')
		served[i] = True
	if q[0] == '2':
		while served[last_served]:
			last_served = last_served + 1
		print(last_served, end=' ')
		served[last_served] = True
	if q[0] == '1':
		heappush(heap, (-int(q[1]), client_number))
		served.append(False)
		client_number += 1


import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict, deque, Counter
from itertools import permutations
from math import sqrt, gcd, pi, factorial
from functools import reduce
from sys import stdin
from bisect import bisect_right, bisect_left
from copy import copy
from heapq import heapify, heappop, heappush

def solve(n, queries):
	p = []
	heapify(p)
	served_indexes = set()
	unserved_pairs = deque([])
	ret = []
	cnt = 0
	for (i, query) in enumerate(queries):
		if query[0] == 1:
			cnt += 1
			heappush(p, [-query[1], cnt])
			unserved_pairs.append([cnt, query[1]])
		elif query[0] == 2:
			while True:
				(index, value) = unserved_pairs.popleft()
				if index in served_indexes:
					continue
				served_indexes.add(index)
				ret.append(index)
				break
		else:
			while True:
				(value, index) = heappop(p)
				if index in served_indexes:
					continue
				served_indexes.add(index)
				ret.append(index)
				break
	return ret
n = int(input())
queries = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, queries)
print(*ans)


from math import *
import threading
import sys
from collections import defaultdict
from pprint import pprint
from heapq import heapify, heappop, heappush
sys.setrecursionlimit(300000)
mod = 10 ** 9
inf = 10 ** 15
yes = 'YES'
no = 'NO'
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def npr(n, r):
	return factorial(n) // factorial(n - r) if n >= r else 0

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val):
	ans = -1
	lb = 0
	ub = len(li) - 1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def pref(li):
	pref_sum = [0]
	for i in li:
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	li = []
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, len(prime)):
		if prime[p]:
			li.append(p)
	return li

def primefactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 2:
		factors.append(n)
	return factors

def prod(li):
	ans = 1
	for i in li:
		ans *= i
	return ans

def dist(a, b):
	d = abs(a[1] - b[1]) + abs(a[2] - b[2])
	return d

def power_of_n(x, n):
	cnt = 0
	while x % n == 0:
		cnt += 1
		x //= n
	return cnt
for _ in range(1):
	heap = []
	heapify(heap)
	n = int(input())
	a = []
	s = set()
	ans = []
	cnt = 1
	ind = 0
	for i in range(n):
		a1 = list(map(int, input().split()))
		if a1[0] == 1:
			num = a1[1]
			a.append(num)
			heappush(heap, (-num, cnt))
			cnt += 1
		elif a1[0] == 2:
			while ind < len(a) and ind + 1 in s:
				ind += 1
			s.add(ind + 1)
			ans.append(ind + 1)
		else:
			(num, j) = heappop(heap)
			while j in s:
				(num, j) = heappop(heap)
			ans.append(j)
			s.add(j)
	print(*ans)


from queue import PriorityQueue, Queue
import sys

class Customer(object):

	def __init__(self, i):
		self.i = i
		self.seen = False

	def __lt__(self, other):
		return self.i < other.i

def parse_input():
	test_count = int(sys.stdin.readline())
	poly_customers = PriorityQueue()
	mono_customers = Queue()
	i = 0
	for _ in range(test_count):
		line = sys.stdin.readline().strip()
		if line.startswith('1'):
			(a, b) = line.split(' ', maxsplit=1)
			(a, b) = (int(a), int(b))
			i += 1
			c = Customer(i)
			poly_customers.put((-b, c))
			mono_customers.put(c)
		else:
			c = int(line)
			if c == 2:
				yield get_mono(mono_customers)
			elif c == 3:
				yield get_poly(poly_customers)
			else:
				raise Exception

def get_mono(mono_customers):
	c = mono_customers.get()
	while c.seen:
		c = mono_customers.get()
	c.seen = True
	return c.i

def get_poly(poly_customers):
	(_, c) = poly_customers.get()
	while c.seen:
		(_, c) = poly_customers.get()
	c.seen = True
	return c.i

def main():
	for o in parse_input():
		sys.stdout.write(f'{o}\n')
main()


import sys
input = sys.stdin.readline
from heapq import heappush, heappop
t = int(input())
hp = []
idx = 1
seen = [0] * (t + 1)
ser = 1
for _ in range(t):
	q = list(map(int, input().split()))
	if q[0] == 1:
		heappush(hp, (-q[1], idx))
		idx += 1
	elif q[0] == 2:
		while seen[ser]:
			ser += 1
		print(ser)
		seen[ser] = 1
		ser += 1
	else:
		while hp and seen[hp[0][1]]:
			heappop(hp)
		(_, i) = heappop(hp)
		print(i)
		seen[i] = 1


from collections import deque
from heapq import heapify, heappop, heappush
mono = deque()
poly = []
a = 1
seen = set()
for _ in range(int(input())):
	while mono and mono[0] in seen:
		mono.popleft()
	while poly and poly[0][1] in seen:
		heappop(poly)
	p = list(map(int, input().split()))
	if p[0] == 1:
		mono.append(a)
		heappush(poly, (-p[1], a))
		a += 1
	elif p[0] == 2:
		q = mono.popleft()
		seen.add(q)
		print(q, end=' ')
	else:
		q = heappop(poly)[1]
		print(q, end=' ')
		seen.add(q)


import heapq
t = int(input())
served = set()
served_list = []
h = []
heapq.heapify(h)
q = []
j = 0
k = 0
for query in range(t):
	x = [int(s) for s in input().split(' ')]
	if x[0] == 1:
		heapq.heappush(h, (-x[1], k))
		q.append((x[1], k))
		k += 1
	elif x[0] == 2:
		while q[j][1] in served:
			j += 1
		served.add(q[j][1])
		served_list.append(q[j][1])
	elif x[0] == 3:
		z = heapq.heappop(h)
		while z[1] in served:
			z = heapq.heappop(h)
		served.add(z[1])
		served_list.append(z[1])
print(*[x + 1 for x in served_list])


import heapq
q = int(input())
mono_queue = []
poly_queue = []
served = dict()
ans = []
count = 0
for query in range(1, q + 1):
	read_line = input().split(' ')
	if read_line[0] == '1':
		m = int(read_line[1])
		count += 1
		heapq.heappush(mono_queue, (count, -m))
		heapq.heappush(poly_queue, (-m, count))
	elif read_line[0] == '2':
		next_to_serve = heapq.heappop(mono_queue)[0]
		while next_to_serve in served.keys():
			next_to_serve = heapq.heappop(mono_queue)[0]
		ans.append(next_to_serve)
		served[next_to_serve] = True
	elif read_line[0] == '3':
		next_to_serve = heapq.heappop(poly_queue)[1]
		while next_to_serve in served.keys():
			next_to_serve = heapq.heappop(poly_queue)[1]
		ans.append(next_to_serve)
		served[next_to_serve] = True
print(' '.join([str(x) for x in ans]))


lines = int(input())
import sys
from heapq import heappush, heappop, heapify

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))
arr = []
ans = []
visited = []
h = []
heapify(h)
index = 0
oddindex = 0
for line in range(lines):
	temparr = get_ints()
	n = temparr[0]
	if n == 1:
		m = temparr[1]
		arr.append(m)
		mm = -1 * m
		heappush(h, (mm, index))
		index += 1
		visited.append(0)
	elif n == 2:
		nn = len(arr)
		for i in range(oddindex, nn):
			if visited[i] == 0:
				ans.append(i + 1)
				visited[i] = 1
				break
		oddindex = i
	elif n == 3:
		while True:
			newitem = heappop(h)
			newindex = newitem[1]
			if visited[newindex] == 1:
				continue
			visited[newindex] = 1
			ans.append(newindex + 1)
			break
newans = [str(_) for _ in ans]
print(' '.join(newans))


import sys
import heapq
from heapq import heappush, heappop
import math
from sys import stdin, stdout

def sieve(N):
	primeNumbers = [True] * (N + 1)
	primeNumbers[0] = False
	primeNumbers[1] = False
	i = 2
	while i * i <= N:
		j = i
		if primeNumbers[j]:
			while j * i <= N:
				primeNumbers[j * i] = False
				j += 1
		i += 1
	return primeNumbers

def getPrime(N):
	primes = sieve(N)
	result = []
	for i in range(len(primes)):
		if primes[i]:
			result.append(i)
	return result

def factor(N):
	factors = []
	i = 1
	while i * i <= N:
		if N % i == 0:
			factors.append(i)
			if i != N // i:
				factors.append(N // i)
		i += 1
	return sorted(factors)

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def extendedGcd(a, b):
	if a < b:
		return extendedGcd(b, a)
	if b == 0:
		return [a, 1, 0]
	res = extendedGcd(b, a % b)
	x = res[2]
	y = res[1] - math.floor(a / b) * res[2]
	res[1] = x
	res[2] = y
	return res

def iterativeModularFunc(a, b, c):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % c
		a = a * a % c
		b = b // 2
	return res

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(input())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def Solution():
	heap = []
	hm = []
	idx = 0
	res = []
	for _ in range(get_int()):
		q = input()
		if q[0] == '1':
			ip = list(map(int, q.split()))
			v = ip[1]
			hm.append(0)
			heappush(heap, (-1 * v, len(hm) - 1))
		elif q[0] == '2':
			while hm[idx] == 1:
				idx += 1
			hm[idx] = 1
			res.append(idx + 1)
		else:
			while hm[heap[0][1]] == 1:
				heappop(heap)
			itm = heappop(heap)
			hm[itm[1]] = 1
			res.append(itm[1] + 1)
	print(*res)

def main():
	Solution()
main()


import heapq
from collections import deque

class C:

	def __init__(self, n, m) -> None:
		self.n = n
		self.m = m

	def __lt__(self, other):
		if self.m == other.m:
			return self.n < other.n
		return self.m > other.m
ch = []
ca = deque([])
cn = 0
rez = []
ads = set()
for _ in range(int(input())):
	q = input()
	if q[0] == '1':
		(_, m) = map(int, q.split())
		cn += 1
		c = C(cn, m)
		ca.append(c)
		heapq.heappush(ch, c)
	elif q[0] == '2':
		c = ca.popleft()
		while c in ads:
			c = ca.popleft()
		rez.append(c)
		ads.add(c)
	else:
		c = heapq.heappop(ch)
		while c in ads:
			c = heapq.heappop(ch)
		rez.append(c)
		ads.add(c)
print(*map(lambda o: o.n, rez))


import heapq
n = int(input())
visited = set()
h = []
heapq.heapify(h)
queue = []
order = 1
j = 0
ans = []
for i in range(n):
	a = list(map(int, input().split()))
	if len(a) == 2:
		heapq.heappush(h, (-a[1], order))
		queue.append(order)
		order += 1
	elif a[0] == 2:
		while j < len(queue):
			if queue[j] not in visited:
				visited.add(queue[j])
				ans.append(queue[j])
				j += 1
				break
			j += 1
	else:
		(a, b) = heapq.heappop(h)
		while b in visited:
			(a, b) = heapq.heappop(h)
		ans.append(b)
		visited.add(b)
for i in ans:
	print(i, end=' ')
print()


from collections import deque, Counter
from collections import defaultdict as dfd
from bisect import bisect, bisect_left
from math import sqrt, gcd, ceil, factorial, log2
from heapq import heapify, heappush, heappop
MOD = 10 ** 9 + 7
inf = float('inf')
ans_ = []

def nin():
	return int(input())

def ninf():
	return int(file.readline())

def st():
	return input().strip()

def stf():
	return file.readline().strip()

def read():
	return list(map(int, input().strip().split()))

def readf():
	return list(map(int, file.readline().strip().split()))

def readfl():
	return list(map(float, input().strip().split()))

def readffl():
	return list(map(float, file.readline().strip().split()))

def solve():
	arr = []
	heap = []
	i = 0
	ans = ''
	for j in range(nin()):
		tem = read()
		if len(tem) > 1:
			(a, b) = tem
		else:
			a = tem[0]
		if a == 2:
			while i < len(arr) and arr[i] == -1:
				i += 1
			ans += str(i + 1) + ' '
			arr[i] = -1
		elif a == 3:
			while heap and arr[heap[0][1]] == -1:
				heappop(heap)
			curr = heappop(heap)[1]
			arr[curr] = -1
			ans += str(curr + 1) + ' '
		else:
			arr.append(j)
			heappush(heap, [-b, len(arr) - 1])
	ans_.append(ans)
solve()
for i in ans_:
	print(i)


from sys import stdin
from queue import Queue, PriorityQueue
n = int(stdin.readline())
q = PriorityQueue()
que = Queue()
done = set()
counter = 1
for i in range(n):
	s = stdin.readline()
	if len(s) > 2:
		(c, p) = map(int, s.split())
		p = 5 * 10 ** 5 - p
		q.put((p, counter))
		que.put(counter)
		counter += 1
	else:
		s = int(s)
		if s == 2:
			first = que.get()
			while first in done:
				first = que.get(0)
			done.add(first)
			print(first, end=' ')
		else:
			first = q.get()
			while first[1] in done:
				first = q.get()
			done.add(first[1])
			print(first[1], end=' ')


import heapq
from collections import deque
queue = deque()
heap = []
hmap = {}

def process_new_client(I, m):
	queue.append(I)
	heapq.heappush(heap, (-1 * m, I))

def served_by_1():
	res = None
	while True:
		res = queue.popleft()
		if res not in hmap:
			break
	hmap[res] = True
	return res

def served_by_2():
	res = None
	while True:
		res = heapq.heappop(heap)
		if res[1] not in hmap:
			break
	hmap[res[1]] = True
	return res[1]

def main():
	Q = int(input())
	I = 1
	for c in range(Q):
		inp = input().rstrip().split(' ')
		if len(inp) == 2:
			process_new_client(I, int(inp[1]))
			I += 1
		elif inp[0] == '2':
			res = served_by_1()
			print(res)
		else:
			res = served_by_2()
			print(res)
main()


from sys import stdin, stdout
SKIP = 0

class Element:

	def __init__(self, x, i):
		self.index = i
		self.value = x

	def __gt__(self, other):
		if self.value > other.value:
			return True
		if self.value == other.value and self.index < other.index:
			return True
		return False

	def __str__(self):
		return f'[{self.value}, {self.index}]'

class Heap:

	def __init__(self):
		self.a = [Element(0, 0)]

	def insert(self, x):
		a = self.a
		a.append(x)
		i = len(self.a) - 1
		while i > 1:
			parent_i = self._parent_index(i)
			if a[i] > a[parent_i]:
				(a[i], a[parent_i]) = (a[parent_i], a[i])
			i = parent_i

	def get_max(self):
		return self.a[1]

	def pop_max(self):
		a = self.a
		x = a[1]
		last = a.pop()
		if len(a) > 1:
			a[1] = last
			i = 1
			while i < len(a):
				left_child_i = self._left_child_index(i)
				if left_child_i >= len(a):
					left_child_i = 0
				right_child_i = self._right_child_index(i)
				if right_child_i >= len(a):
					right_child_i = 0
				max_child_i = left_child_i if a[left_child_i] > a[right_child_i] else right_child_i
				if a[max_child_i] > a[i]:
					(a[max_child_i], a[i]) = (a[i], a[max_child_i])
					i = max_child_i
				else:
					break
		return x

	@staticmethod
	def _parent_index(i):
		return i // 2

	@staticmethod
	def _left_child_index(i):
		return 2 * i

	@staticmethod
	def _right_child_index(i):
		return 2 * i + 1

	def print(self):
		print('\n======')
		max_in_a_row = 1
		now_in_a_row = 0
		for i in range(1, len(self.a)):
			x = self.a[i]
			now_in_a_row += 1
			end_ch = ' '
			if now_in_a_row == max_in_a_row:
				end_ch = '\n'
				max_in_a_row *= 2
				now_in_a_row = 0
			print(x, end=end_ch)
		print('\n======')

	def __len__(self):
		return len(self.a) - 1

class Queue:

	def __init__(self):
		self.a = []
		self.index = 0

	def _skip_used(self):
		while self.a[self.index] == SKIP:
			self.index += 1

	def get_max(self):
		self._skip_used()
		return self.a[self.index]

	def pop_max(self):
		self._skip_used()
		self.index += 1
		return self.a[self.index - 1]

	def insert(self, x):
		self.a.append(x)

	def mark_as_skipped(self, element):
		self.a[element.index] = SKIP

def main():
	policarp_queue = Heap()
	monocarp_queue = Queue()
	monocarp_done = Heap()
	input = stdin.readline
	n = int(input())
	i = 0
	for _ in range(n):
		r = [int(x) for x in input().split()]
		if r[0] == 1:
			element = Element(r[1], i)
			i += 1
			policarp_queue.insert(element)
			monocarp_queue.insert(element)
		elif r[0] == 2:
			element = monocarp_queue.pop_max()
			monocarp_done.insert(element)
			stdout.write(str(element.index + 1) + ' ')
		else:
			while len(monocarp_done) > 0 and monocarp_done.get_max() == policarp_queue.get_max():
				policarp_queue.pop_max()
				monocarp_done.pop_max()
			element = policarp_queue.pop_max()
			monocarp_queue.mark_as_skipped(element)
			stdout.write(str(element.index + 1) + ' ')
main()


from sys import stdin
import heapq
q = int(stdin.readline())
endlis = []
mono = 0
hq = []
ans = []
for loop in range(q):
	query = input()
	if query[0] == '1':
		(tmp, m) = map(int, query.split())
		endlis.append(0)
		heapq.heappush(hq, (-1 * m, len(endlis) - 1))
	elif query[0] == '2':
		while endlis[mono] == 1:
			mono += 1
		ans.append(mono + 1)
		endlis[mono] = 1
	else:
		while endlis[hq[0][1]] == 1:
			heapq.heappop(hq)
		(tmp, ind) = heapq.heappop(hq)
		ans.append(ind + 1)
		endlis[ind] = 1
print(*ans)


import sys
import heapq
input = sys.stdin.readline
getint = lambda : int(input())
getints = lambda : [int(a) for a in input().split()]
served = []
time_cursor = 0
customer_count = 0
list_time = []
list_money = []

def add_customer(val):
	global list_time
	global customer_count
	global list_money
	global time_cursor
	global served
	list_time.append(val)
	heapq.heappush(list_money, (-val, customer_count))
	customer_count += 1

def deque_first():
	global list_time
	global customer_count
	global list_money
	global time_cursor
	global served
	while list_time[time_cursor] == -1:
		time_cursor += 1
	served.append(time_cursor + 1)
	list_time[time_cursor] = -1
	time_cursor += 1

def deque_best():
	global list_time
	global customer_count
	global list_money
	global time_cursor
	global served
	(_, idx) = heapq.heappop(list_money)
	while list_time[idx] == -1:
		(_, idx) = heapq.heappop(list_money)
	list_time[idx] = -1
	served.append(idx + 1)

def solve():
	global served
	q = getint()
	for i in range(q):
		raw = getints()
		if raw[0] == 1:
			add_customer(raw[1])
		elif raw[0] == 2:
			deque_first()
		else:
			deque_best()
	print(' '.join([str(i) for i in served]))
solve()


from queue import PriorityQueue

def main():
	queries = int(input())
	customer_pqueue = PriorityQueue()
	marked = [None]
	out_list = []
	customer_id = 0
	count = 1
	for _ in range(queries):
		query = input()
		if not query.isdigit():
			customer_id += 1
			money_amount = int(query.split()[1])
			customer_pqueue.put((-1 * money_amount, customer_id))
			marked.append(False)
		elif query == '2':
			while marked[count] == True:
				count += 1
			marked[count] = True
			out_list.append(str(count))
		elif query == '3':
			while customer_pqueue:
				customer = customer_pqueue.get()
				id = customer[1]
				if marked[id] == False:
					out_list.append(str(id))
					marked[id] = True
					break
	print(' '.join(out_list))
main()


import heapq
q = int(input())
a = []
b = []
heapq.heapify(a)
heapq.heapify(b)
a_done = set()
b_done = set()
answer = []
count = 0
for i in range(q):
	query = input()
	if len(query) == 1:
		if query == '2':
			while True:
				temp = heapq.heappop(a)
				if (-temp[1], temp[0]) not in b_done:
					answer.append(temp[0] + 1)
					a_done.add(temp)
					break
				else:
					continue
		else:
			while True:
				temp = heapq.heappop(b)
				if (temp[1], -temp[0]) not in a_done:
					answer.append(temp[1] + 1)
					b_done.add(temp)
					break
				else:
					continue
	else:
		(q, m) = list(map(int, query.split()))
		heapq.heappush(a, (count, m))
		heapq.heappush(b, (-m, count))
		count += 1
print(*answer)


import sys
input = sys.stdin.readline
from heapq import heappop, heappush
ind = 1
x = 1
q = int(input())
heap = []
ans = []
seen = [0] * (q + 1)
for i in range(q):
	arr = list(map(int, input().split()))
	if arr[0] == 1:
		heappush(heap, (-arr[1], ind))
		ind += 1
	elif arr[0] == 2:
		while seen[x]:
			x += 1
		ans.append(x)
		seen[x] = 1
		x += 1
	else:
		while heap and seen[heap[0][1]]:
			heappop(heap)
		a = heappop(heap)
		ans.append(a[1])
		seen[a[1]] = 1
print(' '.join((str(x) for x in ans)))


import os
import math
import statistics
import heapq
true = True
false = False
from functools import reduce
is_dev = 'vscode' in os.environ
if is_dev:
	inF = open('in.txt', 'r')
	outF = open('out.txt', 'w')

def ins():
	return list(map(int, input_().split(' ')))

def inss():
	return list(input_().split(' '))

def input_():
	if is_dev:
		return inF.readline()[:-1]
	else:
		return input()

def ranin():
	return range(int(input_()))

def print_(data):
	if is_dev:
		outF.write(str(data) + '\n')
	else:
		print(data)
epsilon = 1e-07
customers = []
heapq.heapify(customers)
i = 1
j = 1
served = [False] * (5 * 10 ** 5 + 2)
result = []
for _ in range(int(input_())):
	a = ins()
	if a[0] == 1:
		heapq.heappush(customers, (-a[1], i))
		i += 1
	elif a[0] == 2:
		while served[j]:
			j += 1
		served[j] = True
		result.append(j)
		j += 1
	elif a[0] == 3:
		customer = heapq.heappop(customers)
		while served[customer[1]]:
			customer = heapq.heappop(customers)
		served[customer[1]] = True
		result.append(customer[1])
print_(' '.join(map(str, result)))
if is_dev:
	outF.close()

	def compare_file():
		print(open('out.txt', 'r').read() == open('outactual.txt', 'r').read())
	compare_file()