Chef has opened up a new restaurant. Like every other restaurant, critics critique this place. The Chef wants to gather as much positive publicity as he can. Also, he is very aware of the fact that people generally do not tend to go through all the reviews. So he picks out the positive reviews and posts it on the website of the restaurant. A review is represented by an integer which is the overall rating of the restaurant as calculated by that particular review.
A review is considered to be positive if it is among the top one-third of the total reviews when they are sorted by their rating. For example, suppose the ratings given by 8 different reviews are as follows:

2 8 3 1 6 4 5 7

Then the top one-third reviews will be 8 and 7. Note that we considered one-third to be 8/3=2 top reviews according to integer division. (see Notes)
So here is what the Chef wants from you: Given the reviews(ratings) by different critics, the Chef needs you to tell him what is the minimum rating that his website will be displaying. For example in the above case, the minimum rating that will be displayed is 7. Also, different critics keep reviewing the restaurant continuosly. So the new reviews keep coming in. The Chef wants your website ratings to be up-to-date. So you should keep updating the ratings there. At any point of time, the Chef might want to know the minimum rating being displayed. You'll have to answer that query. An interesting thing to note here is that a review might be in the website for some time and get knocked out later because of new better reviews and vice-versa.
Notes: To be precise, the number of reviews displayed website will be floor(n / 3), where n denotes the current number of all reviews.

------ Input ------ 

First line of the input file consists of a single integer N, the number of operations to follow. The next N lines contain one operation each on a single line. An operation can be of 2 types:

1 x : Add a review with rating 'x' to the exisiting list of reviews (x is an integer)

2 : Report the current minimum rating on the website 

------ Output ------ 

For every test case, output a single integer each for every operation of type 2 mentioned above. If no review qualifies as a positive review, print "No reviews yet".

------ Constraints ------ 

1 ≤ N ≤ 250000
1 ≤ x ≤ 1000000000

----- Sample Input 1 ------ 
10
1 1
1 7
2
1 9
1 21
1 8
1 5
2
1 9
2
----- Sample Output 1 ------ 
No reviews yet
9
9
----- explanation 1 ------ 
Before the first query of the Chef, i.e. the first operation of type 2 in the input, the only ratings were 1 & 7. Thus, there will be total of 2/3 = 0 positive ratings. For the next two, the ratings list now looks like: 1 5 7 8 9 21. Hence, top one-third will have 6/3 = 2 ratings as positive. And lowest displayed rating will be 9. Similarly for the last operation of type 2. Note that there are two ratings of the same value 9 now and only one of them can be in the top reviews. In such a case, you can choose any one of them.

Difficulty: MEDIUM_HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
import queue
upper = queue.PriorityQueue()
under = queue.PriorityQueue()
n = int(input())
nreview = 0
for _ in range(n):
	s = input()
	if len(s) != 1:
		(a, b) = map(int, s.split())
		nreview += 1
		if nreview < 3:
			under.put(-b)
		elif nreview == 3:
			under.put(-b)
			upper.put(-under.get())
		else:
			c = upper.queue[0]
			d = -under.queue[0]
			if upper.qsize() == nreview // 3:
				if c >= b:
					under.put(-b)
				else:
					upper.get()
					upper.put(b)
					under.put(-c)
			elif d > b:
				upper.put(-under.get())
				under.put(-b)
			else:
				upper.put(b)
	elif nreview < 3:
		print('No reviews yet')
	else:
		print(upper.queue[0])


import heapq
import sys

def FILE_IO():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	N = int(input())
	no_reviews = 0
	min_heap = []
	max_heap = []
	for _ in range(N):
		line = input()
		if line[0] == '1':
			x = int(line[2:])
			no_reviews += 1
			if len(min_heap) != 0 and min_heap[0] < x:
				heapq.heappush(min_heap, x)
				heapq.heappush(max_heap, -heapq.heappop(min_heap))
			else:
				heapq.heappush(max_heap, -x)
			if no_reviews % 3 == 0:
				heapq.heappush(min_heap, -heapq.heappop(max_heap))
		elif len(min_heap) == 0:
			print('No reviews yet')
		else:
			print(min_heap[0])
solve()


from heapq import *
n = 0
(minheap, maxheap) = ([], [])
for _ in range(int(input())):
	arr = list(map(int, input().split()))
	if len(arr) == 2:
		heappush(minheap, arr[1])
		n += 1
		if len(minheap) > n // 3:
			heappush(maxheap, -heappop(minheap))
		elif -maxheap[0] > minheap[0]:
			heappush(minheap, -heappop(maxheap))
			heappush(maxheap, -heappop(minheap))
	elif n < 3:
		print('No reviews yet')
	else:
		print(minheap[0])


import heapq
h = []
ot = []
c = 0
n = int(input())
for i in range(n):
	lis = [int(o) for o in input().split()]
	a = lis[0]
	if a == 1:
		b = lis[1]
		c += 1
		if ot and ot[0] < b:
			heapq.heappush(h, -heapq.heappop(ot))
			heapq.heappush(ot, b)
		else:
			heapq.heappush(h, -b)
		if c % 3 == 0:
			heapq.heappush(ot, -heapq.heappop(h))
	else:
		d = c // 3
		if d == 0:
			print('No reviews yet')
		else:
			print(ot[0])


import heapq
n = int(input())
h = []
length = 0
popTemp = []
while n > 0:
	rawInput = list(map(int, input().split()))
	if rawInput[0] == 1:
		length += 1
		val = rawInput[1]
		if length > 3 and h[0] < val and (length % 3 != 0):
			val = heapq.heapreplace(h, val)
		heapq.heappush(popTemp, -1 * val)
		if length % 3 == 0:
			heapq.heappush(h, -1 * heapq.heappop(popTemp))
	elif length >= 3:
		print(h[0])
	else:
		print('No reviews yet', end='\n')
	n -= 1


import heapq
n = int(input())
res = []
res1 = []
ct = 0
heapq.heapify(res)
heapq.heapify(res1)
for i in range(n):
	lis = list(map(int, input().split()))
	if len(lis) == 1:
		j = ct // 3
		if j == 0:
			print('No reviews yet')
		else:
			print(res[0])
	else:
		x = lis[1]
		heapq.heappush(res1, -x)
		ct += 1
		j = ct // 3
		if j == 0:
			continue
		if len(res) == j:
			if x > res[0]:
				z = heapq.heappop(res)
				heapq.heappush(res, x)
				heapq.heappop(res1)
				heapq.heappush(res1, -z)
		else:
			m = heapq.heappop(res1)
			heapq.heappush(res, -m)


import heapq
n = int(input())
size = 0
(minheap, maxheap) = ([], [])
for i in range(n):
	query = input()
	if query == '2':
		if size < 3:
			print('No reviews yet')
		else:
			print(minheap[0])
	else:
		(x, val) = query.split()
		val = int(val)
		size += 1
		heapq.heappush(maxheap, -val)
		if size >= 3:
			if size % 3 == 0:
				heapq.heappush(minheap, -heapq.heappop(maxheap))
			elif -maxheap[0] > minheap[0]:
				replaced_val = heapq.heapreplace(minheap, -heapq.heappop(maxheap))
				heapq.heappush(maxheap, -replaced_val)


import heapq
import math

class RestaurantRating:

	def process(self):
		n = int(input())
		heap_max = []
		heap_min = []
		for _ in range(n):
			data = input()
			if data[0] == '1':
				v = int(data.split()[1])
				if len(heap_min) > 0 and heap_min[0] < v:
					temp = heap_min[0]
					heapq.heappop(heap_min)
					heapq.heappush(heap_min, v)
					v = temp
				heapq.heappush(heap_max, -v)
				if (len(heap_max) + len(heap_min)) % 3 == 0:
					heapq.heappush(heap_min, -heap_max[0])
					heapq.heappop(heap_max)
				elif len(heap_min) > 0 and -heap_max[0] > heap_min[0]:
					(max_arr, min_top_k) = (-heap_max[0], heap_min[0])
					heapq.heappop(heap_max)
					heapq.heappop(heap_min)
					heapq.heappush(heap_max, -min_top_k)
					heapq.heappush(heap_min, max_arr)
			elif len(heap_min) == 0:
				print('No reviews yet')
			else:
				print(heap_min[0])
restaurantRate = RestaurantRating()
restaurantRate.process()


import heapq

def method_2():
	N = int(input())
	min_heap = []
	max_heap = []
	size_post = 0
	for _ in range(N):
		query = input()
		if query == '2':
			if size_post > 2:
				print(min_heap[0])
			else:
				print('No reviews yet')
		else:
			(op, val_string) = query.split()
			val = int(val_string)
			size_post += 1
			if size_post == 1:
				heapq.heappush(max_heap, -val)
				continue
			if -max_heap[0] >= val:
				heapq.heappush(max_heap, -val)
			else:
				heapq.heappush(min_heap, val)
			if len(min_heap) < size_post // 3:
				heapq.heappush(min_heap, -heapq.heappop(max_heap))
			elif len(min_heap) > size_post // 3:
				heapq.heappush(max_heap, -heapq.heappop(min_heap))
method_2()


import heapq
N = int(input())
min_heap_top = []
max_heap_remain = []
size_post = 0
for _ in range(N):
	input_text = input()
	if input_text == '2':
		if size_post < 3:
			print('No reviews yet')
		else:
			print(-max_heap_remain[0])
	else:
		(operation, value) = map(int, input_text.split())
		size_post += 1
		if len(max_heap_remain) > 2:
			if -max_heap_remain[0] > value:
				heapq.heappush(max_heap_remain, -value)
			else:
				heapq.heappush(min_heap_top, value)
			while len(min_heap_top) > size_post // 3 - 1:
				pop_value = heapq.heappop(min_heap_top)
				heapq.heappush(max_heap_remain, -pop_value)
			while len(min_heap_top) < size_post // 3 - 1:
				pop_value = heapq.heappop(max_heap_remain)
				heapq.heappush(min_heap_top, -pop_value)
		else:
			heapq.heappush(max_heap_remain, -value)


import heapq
N = int(input())
(heap1, minheap) = ([], [])
n = 0
for _ in range(N):
	z = input().split()
	if int(z[0]) == 2:
		if n < 3:
			print('No reviews yet')
		else:
			print(minheap[0])
	else:
		n += 1
		x = int(z[1])
		if n > 3 and minheap[0] < x and (n % 3 != 0):
			x = heapq.heapreplace(minheap, x)
		heapq.heappush(heap1, -x)
		if n % 3 == 0:
			heapq.heappush(minheap, -heapq.heappop(heap1))


import heapq
N = int(input())
min_heap = []
max_heap = []
review_count = 0
for _ in range(N):
	query = list(map(int, input().split()))
	if query[0] == 1:
		value = query[1]
		review_count += 1
		if min_heap and min_heap[0] < value:
			heapq.heappush(min_heap, value)
			heapq.heappush(max_heap, -heapq.heappop(min_heap))
		else:
			heapq.heappush(max_heap, -value)
		if review_count % 3 == 0:
			heapq.heappush(min_heap, -heapq.heappop(max_heap))
	if query[0] == 2:
		if min_heap:
			print(min_heap[0])
		else:
			print('No reviews yet')


import heapq
n = int(input())
number_reviews = 0
all_reviews = []
heapq.heapify(all_reviews)
highest_reviews = []
heapq.heapify(highest_reviews)
for i in range(n):
	inp = list(map(int, input().split()))
	if inp[0] == 1:
		number_reviews += 1
		heapq.heappush(all_reviews, -inp[1])
		top = number_reviews // 3
		while len(highest_reviews) < top:
			rating = heapq.heappop(all_reviews) * -1
			heapq.heappush(highest_reviews, rating)
		if top > 0:
			right = highest_reviews[0]
			left = all_reviews[0] * -1
			while right < left:
				heapq.heappush(all_reviews, right * -1)
				heapq.heappush(highest_reviews, left)
				left = heapq.heappop(all_reviews)
				right = heapq.heappop(highest_reviews)
			val = highest_reviews[0]
	else:
		top = number_reviews // 3
		if top == 0:
			print('No reviews yet')
			continue
		else:
			print(highest_reviews[0])


from heapq import heappush, heappop, heapify, heapreplace
h = []
n = 0
new = []
for t in range(int(input())):
	a = input()
	if a[0] == '1':
		(a, val) = map(int, a.split())
	else:
		a = int(a)
	if a == 1:
		n += 1
		if n > 3 and h[0] < val and (n % 3 != 0):
			val = heapreplace(h, val)
		heappush(new, -1 * val)
		if n % 3 == 0:
			heappush(h, -1 * heappop(new))
	elif n >= 3:
		print(h[0])
	else:
		print('No reviews yet')


from bisect import insort
import heapq as he
size = 0
minheap = []
maxheap = []
for _ in range(int(input())):
	li = list(map(int, input().split()))
	if li[0] == 2:
		if size < 3:
			print('No reviews yet')
			continue
		print(minheap[0])
	else:
		size += 1
		if size % 3 == 0:
			he.heappush(maxheap, -li[1])
			he.heappush(minheap, -he.heappop(maxheap))
		elif size > 3:
			if li[1] > minheap[0]:
				he.heappush(maxheap, -he.heappop(minheap))
				he.heappush(minheap, li[1])
			else:
				he.heappush(maxheap, -li[1])
		else:
			he.heappush(maxheap, -li[1])


import heapq
import math
n = int(input())
A = []
B = []
temp = 0
for _ in range(n):
	q = input().split()
	if len(q) > 1:
		(a, b) = map(int, q)
	else:
		a = map(int, q)
	if a == 1:
		k = (len(A) + 1 + len(B)) // 3
		if k > len(B):
			heapq.heappush(A, -b)
			heapq.heappush(B, -heapq.heappop(A))
		elif len(B) > 0 and b > B[0]:
			heapq.heappush(B, b)
			heapq.heappush(A, -heapq.heappop(B))
		else:
			heapq.heappush(A, -b)
	elif len(B) == 0:
		print('No reviews yet')
	else:
		print(B[0])


import heapq
N = int(input())
max_h = []
min_h = []
i = 0
for _ in range(N):
	operation = list(input().split())
	if operation[0] == '1':
		review = int(operation[1])
		i += 1
		if i % 3 == 0:
			if review > -max_h[0]:
				heapq.heappush(min_h, review)
			else:
				heapq.heappush(min_h, -heapq.heappop(max_h))
				heapq.heappush(max_h, -review)
		elif len(min_h) and review > min_h[0]:
			heapq.heappush(max_h, -heapq.heappop(min_h))
			heapq.heappush(min_h, review)
		else:
			heapq.heappush(max_h, -review)
	elif len(min_h) > 0:
		print(min_h[0])
	else:
		print('No reviews yet')


import heapq

class PQEntityMax:

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

	def __lt__(self, other):
		return self.value > other.value
n = int(input())
count = 0
pqMax = []
pqMin = []
for i in range(n):
	data = list(map(int, input().split()))
	type = data[0]
	if type == 1:
		count += 1
		if count // 3 != len(pqMin):
			if data[1] >= pqMax[0].value:
				heapq.heappush(pqMin, data[1])
			else:
				t = heapq.heappop(pqMax)
				heapq.heappush(pqMax, PQEntityMax(data[1]))
				heapq.heappush(pqMin, t.value)
		elif len(pqMin) > 0 and data[1] > pqMin[0]:
			h = heapq.heappop(pqMin)
			heapq.heappush(pqMax, PQEntityMax(h))
			heapq.heappush(pqMin, data[1])
		else:
			heapq.heappush(pqMax, PQEntityMax(data[1]))
	elif count < 3:
		print('No reviews yet')
	else:
		print(pqMin[0])


import heapq as h
import sys
import math
from collections import defaultdict
import bisect

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

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

def input():
	return sys.stdin.readline().strip()
maxi = []
mini = []
c = 0
for _ in range(int(input())):
	S = list(input().split(' '))
	if S[0] == '1':
		c += 1
		d = int(S[1])
		if len(mini) == 0 or c // 3 > len(mini):
			h.heappush(maxi, -d)
			h.heappush(mini, abs(h.heappop(maxi)))
		elif mini[0] < d:
			h.heappush(maxi, -h.heappop(mini))
			h.heappush(mini, d)
		else:
			h.heappush(maxi, -d)
	else:
		print(mini[0]) if c >= 3 else print('No reviews yet')


from heapq import heapify, heappush, heappop
li = []
h = []
count = 0
for _ in range(int(input())):
	a = list(map(int, input().split()))
	if a[0] == 1:
		count += 1
		heappush(li, -1 * a[1])
		if len(h) < count // 3:
			heappush(h, -li[0])
			heappop(li)
		if len(h) == 0:
			continue
		elif -li[0] > h[0]:
			temp = h[0]
			heappop(h)
			heappush(h, -li[0])
			heappop(li)
			heappush(li, -temp)
	elif len(h) == 0:
		print('No reviews yet')
	else:
		print(h[0])


import heapq
Q = int(input())
maxheap = []
minheap = []
cnt = 0
for _ in range(Q):
	q = list(map(int, input().split()))
	if q[0] == 1:
		if len(minheap) > 0 and q[1] > minheap[0]:
			heapq.heappush(minheap, q[1])
			top = heapq.heappop(minheap)
			heapq.heappush(maxheap, (-top, top))
		else:
			heapq.heappush(maxheap, (-q[1], q[1]))
		cnt += 1
		temp = cnt // 3
		if len(minheap) < temp:
			top = heapq.heappop(maxheap)
			heapq.heappush(minheap, top[1])
	elif len(minheap) == 0:
		print('No reviews yet')
	else:
		print(minheap[0])


import heapq as hp
h = []
m = []
count = 0
for _ in range(int(input())):
	a = [int(i) for i in input().split()]
	if len(a) == 2:
		count += 1
		x = a[1]
		hp.heappush(m, -x)
		if len(h) < count // 3:
			hp.heappush(h, -m[0])
			hp.heappop(m)
		if len(h) == 0:
			continue
		elif -m[0] > h[0]:
			temp = h[0]
			hp.heappop(h)
			hp.heappush(h, -m[0])
			hp.heappop(m)
			hp.heappush(m, -temp)
	elif len(h) == 0:
		print('No reviews yet')
	else:
		print(h[0])


import heapq
n = int(input())
noReviews = 0
minHeap = []
maxHeap = []
for _ in range(n):
	line = list(map(int, input().split()))
	if line[0] == 1:
		noReviews += 1
		if len(minHeap) != 0 and minHeap[0] < line[1]:
			heapq.heappush(minHeap, line[1])
			heapq.heappush(maxHeap, -heapq.heappop(minHeap))
		else:
			heapq.heappush(maxHeap, -line[1])
		if noReviews % 3 == 0:
			heapq.heappush(minHeap, -heapq.heappop(maxHeap))
	elif len(minHeap) == 0:
		print('No reviews yet')
	else:
		print(minHeap[0])


import heapq as hq
n = int(input())
count = 0
h = []
i = 0
m = []
for g in range(n):
	a = [int(i) for i in input().split()]
	if len(a) == 2:
		hq.heappush(m, -a[1])
		i += 1
		if i // 3 == 0:
			pass
		elif count < i // 3 and i // 3 > 0:
			hq.heappush(h, -m[0])
			count += 1
			hq.heappop(m)
		elif -m[0] > h[0]:
			hq.heappush(h, -m[0])
			temp = h[0]
			hq.heappop(h)
			hq.heappop(m)
			hq.heappush(m, -temp)
	elif i // 3 == 0:
		print('No reviews yet')
	else:
		print(h[0])


from sys import stdin
from heapq import heappush, heappop

def manage_top_reviews(top_reviews, remaining_reviews, x):
	if len(remaining_reviews) == 0:
		heappush(remaining_reviews, -x)
	else:
		top_count = (len(top_reviews) + len(remaining_reviews) + 1) // 3
		if top_count > 0:
			if len(top_reviews) == 0:
				heappush(remaining_reviews, -x)
				heappush(top_reviews, -heappop(remaining_reviews))
			elif len(top_reviews) == top_count:
				if top_reviews[0] < x:
					heappush(remaining_reviews, -heappop(top_reviews))
					heappush(top_reviews, x)
				else:
					heappush(remaining_reviews, -x)
			elif len(top_reviews) < top_count:
				heappush(remaining_reviews, -x)
				heappush(top_reviews, -heappop(remaining_reviews))
		elif top_count == 0:
			heappush(remaining_reviews, -x)
N = int(stdin.readline())
top_reviews = []
remaining_reviews = []
for _ in range(N):
	query = list(map(int, stdin.readline().strip().split(' ')))
	if len(query) == 2:
		query_type = query[0]
		x = query[1]
	else:
		query_type = 2
	if query_type == 1:
		manage_top_reviews(top_reviews, remaining_reviews, x)
	elif query_type == 2:
		if len(top_reviews) == 0:
			print('No reviews yet')
		else:
			print(top_reviews[0])


import heapq
heapMax = []
heapMin = []
n = int(input())
nreviews = 0
for i in range(n):
	a = list(map(int, input().split()))
	if a[0] == 1:
		nreviews += 1
		x = a[1]
		if len(heapMin) != 0 and heapMin[0] < x:
			heapq.heappush(heapMax, -heapq.heappop(heapMin))
			heapq.heappush(heapMin, x)
		else:
			heapq.heappush(heapMax, -x)
		if nreviews % 3 == 0:
			heapq.heappush(heapMin, -heapq.heappop(heapMax))
	elif len(heapMin) == 0:
		print('No reviews yet')
	else:
		print(heapMin[0])


import heapq

class maxHeap:
	value = 0

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

	def __lt__(self, other):
		return self.value > other.value
onethird = []
twothird = []
nopt = int(input())
nrev = 0
for _ in range(nopt):
	inp = list(input().split())
	if len(inp) != 1:
		nrev += 1
		value = int(inp[1])
		if len(onethird) != 0 and value > onethird[0]:
			heapq.heappush(onethird, value)
			value = onethird[0]
			heapq.heappush(twothird, maxHeap(value))
			heapq.heappop(onethird)
		else:
			heapq.heappush(twothird, maxHeap(value))
		if nrev % 3 == 0:
			value = twothird[0].value
			heapq.heappush(onethird, value)
			heapq.heappop(twothird)
	elif nrev < 3:
		print('No reviews yet')
	else:
		print(onethird[0])


import heapq
import math

class PQEntry:

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

	def __lt__(self, other):
		return self.value > other.value
t = int(input(''))
reviews = []
tops = []
cnt = 0
results = []
for i in range(t):
	rq = list(map(int, input('').split()))
	t = rq[0]
	if t == 1:
		cnt += 1
		v = rq[1]
		if len(tops) > 0:
			if v > tops[0]:
				heapq.heappush(reviews, PQEntry(heapq.heappop(tops)))
				heapq.heappush(tops, v)
			else:
				heapq.heappush(reviews, PQEntry(v))
		else:
			heapq.heappush(reviews, PQEntry(v))
		if cnt % 3 == 0:
			heapq.heappush(tops, heapq.heappop(reviews).value)
	elif t == 2:
		if len(tops) > 0:
			results.append(tops[0])
		else:
			results.append('No reviews yet')
for result in results:
	print(result)


import heapq
top3 = []
rest = []
nreviews = 0
n = int(input())
for _ in range(n):
	line = list(map(int, input().split()))
	type = line[0]
	if type == 1:
		x = line[1]
		nreviews += 1
		if len(top3) != 0 and top3[0] < x:
			heapq.heappush(rest, -heapq.heappop(top3))
			heapq.heappush(top3, x)
		else:
			heapq.heappush(rest, -x)
		if nreviews % 3 == 0:
			heapq.heappush(top3, -heapq.heappop(rest))
	elif len(top3) == 0:
		print('No reviews yet')
	else:
		print(top3[0])


n = int(input())
import heapq
minHeap = []
maxHeap = []
i = 0
for _ in range(n):
	lineGrab = list(input().split())
	if lineGrab[0] == '1':
		i += 1
		val = int(lineGrab[1])
		if minHeap != []:
			if val > minHeap[0]:
				x = heapq.heappop(minHeap)
				heapq.heappush(minHeap, val)
				heapq.heappush(maxHeap, -x)
			else:
				heapq.heappush(maxHeap, -val)
		else:
			heapq.heappush(maxHeap, -val)
		if i % 3 == 0:
			y = heapq.heappop(maxHeap)
			heapq.heappush(minHeap, -y)
	elif minHeap:
		print(minHeap[0])
	else:
		print('No reviews yet')


import heapq
t = int(input())
h1 = []
h2 = []
n = 0
while t:
	inp = input().split()
	if inp[0] == '1':
		x = int(inp[1])
		if len(h1) == 0 or h1[0] <= x:
			heapq.heappush(h1, x)
		else:
			heapq.heappush(h2, -x)
		n += 1
		if len(h1) == n // 3 and n == 3:
			heapq.heappush(h2, -heapq.heappop(h1))
		while len(h1) < n // 3:
			heapq.heappush(h1, -heapq.heappop(h2))
		while len(h1) > n // 3:
			heapq.heappush(h2, -heapq.heappop(h1))
	else:
		print('No reviews yet' if n // 3 == 0 else h1[0])
	t -= 1


import heapq
top = []
rest = []
for _ in range(int(input())):
	x = [int(s) for s in input().split()]
	if len(x) == 2:
		curr = -1
		if rest:
			curr = heapq.heappop(rest)
			curr = curr * -1
		if x[1] >= curr:
			if curr != -1:
				heapq.heappush(rest, -1 * curr)
			heapq.heappush(top, x[1])
			if len(top) != (len(rest) + len(top)) // 3:
				shift = heapq.heappop(top)
				heapq.heappush(rest, -1 * shift)
		else:
			if curr != -1:
				heapq.heappush(rest, -1 * curr)
			heapq.heappush(rest, -1 * x[1])
			if len(top) != (len(rest) + len(top)) // 3:
				shift = heapq.heappop(rest)
				heapq.heappush(top, -1 * shift)
	elif (len(top) + len(rest)) // 3 > 0:
		ans = heapq.heappop(top)
		print(ans)
		heapq.heappush(top, ans)
	else:
		print('No reviews yet')


import heapq
n = int(input())
maxh = []
minh = []
l = 0
while n != 0:
	q = list(map(int, input().split()))
	if q[0] == 1:
		x = heapq.heappushpop(minh, q[1])
		heapq.heappush(maxh, -x)
		l += 1
		if l % 3 == 0:
			x = heapq.heappop(maxh)
			heapq.heappush(minh, -x)
	elif len(minh) > 0:
		x = heapq.heappop(minh)
		print(x)
		heapq.heappush(minh, x)
	else:
		print('No reviews yet')
	n -= 1


import heapq
one_third = []
ar = []
n = 0
for _ in range(int(input())):
	query = list(map(int, input().split()))
	q = query[0]
	if q == 1:
		x = query[1]
		n += 1
		if len(one_third) != 0 and one_third[0] < x:
			heapq.heappush(ar, -heapq.heappop(one_third))
			heapq.heappush(one_third, x)
		else:
			heapq.heappush(ar, -x)
		if n % 3 == 0:
			heapq.heappush(one_third, -heapq.heappop(ar))
	elif len(one_third) == 0:
		print('No reviews yet')
	else:
		print(one_third[0])


from heapq import *
n = int(input())
heap1 = []
heap2 = []
t = 0
for _ in range(n):
	k = input()
	if k[0] == '1':
		s = int(k[2:])
		t += 1
		if len(heap1) > 0:
			if s > heap1[0]:
				heappush(heap1, s)
				d = heappop(heap1)
				heappush(heap2, -d)
				continue
		heappush(heap2, -s)
	else:
		tt = t // 3
		if tt == 0:
			print('No reviews yet')
			continue
		while len(heap1) < tt:
			a = heappop(heap2)
			heappush(heap1, -a)
		print(heap1[0])


from heapq import *

def res(kk, n):
	pq_min = []
	pq_max = []
	length = 0
	for op in kk:
		if op[0] == 1:
			heappush(pq_max, -op[1])
			length += 1
			if length % 3 == 0:
				l = heappop(pq_max)
				heappush(pq_min, -l)
			if len(pq_min) != 0:
				l = -pq_max[0]
				m = pq_min[0]
				if l > m:
					heappop(pq_min)
					heappop(pq_max)
					heappush(pq_min, l)
					heappush(pq_max, -m)
		elif length // 3 == 0:
			print('No reviews yet')
		else:
			print(pq_min[0])
n = int(input())
kk = []
for _ in range(n):
	inp = input().strip()
	if len(inp) > 1:
		kk.append(tuple(map(int, inp.split(' '))))
	else:
		kk.append((int(inp), 0))
res(kk, n)


from heapq import heappush, heappop
max_heap = []
min_heap = []
max_heap_size = 0
min_heap_size = 0
for _ in range(int(input())):
	query = list(map(int, input().split()))
	if query[0] == 1:
		if min_heap_size == 0 or query[1] < min_heap[0]:
			heappush(max_heap, query[1] * -1)
			max_heap_size += 1
		else:
			heappush(min_heap, query[1])
			min_heap_size += 1
		if (max_heap_size + min_heap_size) // 3 > min_heap_size:
			heappush(min_heap, heappop(max_heap) * -1)
			min_heap_size += 1
			max_heap_size -= 1
		elif (max_heap_size + min_heap_size) // 3 < min_heap_size:
			heappush(max_heap, heappop(min_heap) * -1)
			max_heap_size += 1
			min_heap_size -= 1
	elif min_heap_size + max_heap_size < 3:
		print('No reviews yet')
	else:
		print(min_heap[0])


from heapq import heappush, heappop
number_of_commands = int(input())
(rating_min_heap, rating_max_heap) = ([], [])
counting = 0
for i in range(number_of_commands):
	commands = list(map(int, input().strip().split(' ')))
	if len(commands) == 2:
		counting += 1
		one_third = counting // 3
		if rating_min_heap and commands[1] > rating_min_heap[0]:
			heappush(rating_min_heap, commands[1])
		else:
			heappush(rating_max_heap, -commands[1])
		while len(rating_min_heap) > one_third:
			heappush(rating_max_heap, -heappop(rating_min_heap))
		while len(rating_max_heap) > counting - one_third:
			heappush(rating_min_heap, abs(heappop(rating_max_heap)))
	elif len(rating_min_heap) == 0:
		print('No reviews yet')
	else:
		print(rating_min_heap[0])


from heapq import *
import sys
maxheap = []
minheap = []
out = ''
for case in range(int(sys.stdin.readline())):
	L = list(map(int, sys.stdin.readline().split()))
	if L[0] == 2:
		total = len(maxheap) + len(minheap)
		if total < 3:
			out += 'No reviews yet\n'
		else:
			N = int(total / 3)
			while len(minheap) < N:
				num = -1 * heappop(maxheap)
				heappush(minheap, num)
			while len(minheap) > 0 and minheap[0] < -1 * maxheap[0]:
				num1 = -1 * heappop(maxheap)
				num2 = -1 * heappop(minheap)
				heappush(minheap, num1)
				heappush(maxheap, num2)
			out += '%d\n' % minheap[0]
	else:
		heappush(maxheap, -1 * L[1])
print(out[:-1])


import heapq

def solution():
	top_reviews = []
	candidate_reviews = []
	N = int(input())
	results = []
	num_of_reviews = 0
	for i in range(N):
		command = input().strip()
		if command.startswith('1'):
			num_of_reviews += 1
			new_review = int(command.split()[1])
			if len(top_reviews) < num_of_reviews // 3:
				if len(candidate_reviews) < 0 or new_review > -candidate_reviews[0]:
					heapq.heappush(top_reviews, new_review)
				else:
					heapq.heappush(top_reviews, -candidate_reviews[0])
					heapq.heappop(candidate_reviews)
					heapq.heappush(candidate_reviews, -new_review)
			elif len(top_reviews) > 0 and new_review > top_reviews[0]:
				heapq.heappush(candidate_reviews, -top_reviews[0])
				heapq.heappop(top_reviews)
				heapq.heappush(top_reviews, new_review)
			else:
				heapq.heappush(candidate_reviews, -new_review)
		elif len(top_reviews) > 0:
			results.append(top_reviews[0])
		else:
			results.append('No reviews yet')
	print(*results, sep='\n')
solution()


import heapq as hp
n = int(input())
h = []
h1 = []
count = 0
for i in range(n):
	line = input()
	if line[0] == '1':
		value = int(line.split(' ')[1])
		hp.heappush(h, -value)
		count += 1
	elif line[0] == '2':
		d = count // 3
		if d == 0:
			print('No reviews yet')
		else:
			while True:
				if len(h1) != d:
					g = hp.heappop(h)
					hp.heappush(h1, -g)
					if -h[0] > h1[0]:
						a = hp.heappop(h)
						b = hp.heappop(h1)
						hp.heappush(h1, -a)
						hp.heappush(h, -b)
				elif -h[0] > h1[0]:
					a = hp.heappop(h)
					b = hp.heappop(h1)
					hp.heappush(h1, -a)
					hp.heappush(h, -b)
				else:
					break
			print(h1[0])


import heapq
pq = []
max_pq = []
n = int(input())
for i in range(n):
	x = input().split()
	type = int(x[0])
	if type == 1:
		heapq.heappush(max_pq, -int(x[1]))
	else:
		size = (len(pq) + len(max_pq)) // 3
		if size == 0:
			print('No reviews yet')
		else:
			while len(pq) < size:
				heapq.heappush(pq, -heapq.heappop(max_pq))
			while pq[0] < -max_pq[0]:
				heapq.heappush(pq, -heapq.heappop(max_pq))
				heapq.heappush(max_pq, -heapq.heappop(pq))
			print(pq[0])


import heapq
n = int(input())
qMin = []
qMax = []
counter = 0
for _ in range(n):
	data = list(map(int, input().split()))
	op = data[0]
	if op == 1:
		counter += 1
		k = counter // 3
		val = data[1]
		if len(qMin) < k:
			maxVal = heapq.heappushpop(qMax, -val)
			heapq.heappush(qMin, -maxVal)
		elif k != 0 and val > qMin[0]:
			minVal = heapq.heappushpop(qMin, val)
			heapq.heappush(qMax, -minVal)
		else:
			heapq.heappush(qMax, -val)
	elif len(qMin) == 0:
		print('No reviews yet')
	else:
		print(qMin[0])


import heapq
n = int(input())
currentN = 0
qMin = []
qMax = []
for _ in range(n):
	data = list(map(int, input().split()))
	op = data[0]
	if op == 1:
		val = data[1]
		currentN += 1
		k = currentN // 3
		if len(qMin) < k:
			heapq.heappush(qMax, -val)
			heapq.heappush(qMin, -heapq.heappop(qMax))
		elif len(qMin) != 0 and val > qMin[0]:
			heapq.heappush(qMin, val)
			heapq.heappush(qMax, -heapq.heappop(qMin))
		else:
			heapq.heappush(qMax, -val)
	elif len(qMin) == 0:
		print('No reviews yet')
	else:
		print(qMin[0])


import heapq
n = int(input())
size = 0
count = {'h1': 0, 'h2': 0, 'size': 0}
heap1 = []
heap2 = []
heapq.heapify(heap1)
heapq.heapify(heap2)

def addElement(e, h1, h2):
	if count['h1'] != 0 and e > h1[0]:
		heapq.heappush(h1, e)
		count['h1'] += 1
	else:
		heapq.heappush(h2, -e)
		count['h2'] += 1

def rebalance(h1, h2):
	floorval = count['size'] // 3
	if count['h1'] > floorval:
		ele = heapq.heappop(heap1)
		heapq.heappush(heap2, -ele)
		count['h2'] += 1
		count['h1'] -= 1
	elif count['h1'] < floorval:
		ele = heapq.heappop(heap2)
		heapq.heappush(heap1, -ele)
		count['h1'] += 1
		count['h2'] -= 1
while n != 0:
	n -= 1
	temp = [int(x) for x in input().split()]
	if temp[0] == 1:
		ele = temp[1]
		size += 1
		count['size'] += 1
		addElement(ele, heap1, heap2)
		rebalance(heap1, heap2)
	else:
		one_third = size // 3
		if one_third != 0:
			print(heap1[0])
		else:
			print('No reviews yet')


import heapq
top = []
rest = []
total = 0
for _ in range(int(input().strip())):
	ar = list(map(int, input().strip().split()))
	if ar[0] == 2:
		if len(top) == 0:
			print('No reviews yet')
		else:
			print(top[0])
	else:
		total += 1
		r = ar[1]
		if len(top) == 0 or r < top[0]:
			heapq.heappush(rest, -r)
		else:
			heapq.heappush(rest, -heapq.heappop(top))
			heapq.heappush(top, r)
		if len(top) < total // 3:
			heapq.heappush(top, -heapq.heappop(rest))


import queue
import heapq
import math
n = int(input())
min_heap = []
max_heap = []
num_reviews = 0
for i in range(n):
	command = list(map(int, input().split()))
	if command[0] == 1:
		heapq.heappush(min_heap, command[1])
		heapq.heappush(max_heap, -heapq.heappop(min_heap))
		num_reviews += 1
		if len(min_heap) < math.floor(num_reviews / 3):
			heapq.heappush(min_heap, -heapq.heappop(max_heap))
	elif num_reviews > 2:
		print(min_heap[0])
	else:
		print('No reviews yet')


import heapq

def solve():
	minHeap = []
	maxHeap = []
	n = int(input())
	numReview = 0
	while n:
		n -= 1
		line = list(map(int, input().split()))
		t = line[0]
		if t == 1:
			x = line[1]
			numReview += 1
			if len(minHeap) != 0 and minHeap[0] < x:
				heapq.heappush(minHeap, x)
				heapq.heappush(maxHeap, -heapq.heappop(minHeap))
			else:
				heapq.heappush(maxHeap, -x)
			if numReview % 3 == 0:
				heapq.heappush(minHeap, -heapq.heappop(maxHeap))
		elif len(minHeap) == 0:
			print('No reviews yet')
		else:
			print(minHeap[0])
solve()


import heapq
(min_heap, max_heap) = ([], [])
heapq.heapify(min_heap)
heapq.heapify(max_heap)
size = 0
n = int(input())
for i in range(n):
	line = input().split()
	if int(line[0]) == 1:
		size += 1
		x = int(line[1])
		if len(min_heap) >= size // 3:
			heapq.heappush(max_heap, -x)
		else:
			heapq.heappush(min_heap, x)
		if len(min_heap) != 0 and len(max_heap) != 0:
			while -max_heap[0] > min_heap[0]:
				greater = -heapq.heappop(max_heap)
				smaller = heapq.heappop(min_heap)
				heapq.heappush(min_heap, greater)
				heapq.heappush(max_heap, -smaller)
	elif len(min_heap) == 0:
		print('No reviews yet')
	else:
		print(min_heap[0])


import heapq
x = int(input())
minheap = []
maxheap = []
count = 0
for i in range(x):
	data = list(map(int, input().split()))
	if data[0] == 1:
		count += 1
		if len(minheap) > 0 and data[1] > minheap[0]:
			heapq.heappush(minheap, data[1])
			heapq.heappush(maxheap, -heapq.heappop(minheap))
		else:
			heapq.heappush(maxheap, -data[1])
		if count % 3 == 0:
			heapq.heappush(minheap, -heapq.heappop(maxheap))
	elif len(minheap) == 0:
		print('No reviews yet')
	else:
		print(minheap[0])


import heapq

def solve():
	min_queue = []
	max_queue = []
	query = int(input())
	size = 0
	while query:
		line = list(map(int, input().split()))
		if line[0] == 1:
			val = line[1]
			size += 1
			if size % 3 != 0 and size > 3:
				top = min_queue[0]
				if val > top:
					heapq.heappush(min_queue, val)
					heapq.heappush(max_queue, -heapq.heappop(min_queue))
				else:
					heapq.heappush(max_queue, -val)
			else:
				heapq.heappush(max_queue, -val)
				while len(min_queue) < int(size / 3):
					heapq.heappush(min_queue, -heapq.heappop(max_queue))
		elif len(min_queue) == 0:
			print('No reviews yet')
		else:
			print(min_queue[0])
		query -= 1
solve()