monk-and-multiplication

The Monk learned about priority queues recently and asked his teacher for an interesting problem. So his teacher came up with a simple problem. He now has an integer array A. For each index i, he wants to find the product of the largest, second largest and the third largest integer in the range [1,i].
Note: Two numbers can be the same value-wise but they should be distinct index-wise.

Input:
The first line contains an integer N, denoting the number of elements in the array A.
The next line contains N space separated integers, each denoting the ith integer of the array A.

Output:
Print the answer for each index in each line. If there is no second largest or third largest number in the array A upto that index, then print "-1", without the quotes.

Constraints:
1 ≤ N ≤ 100000
0 ≤ A[i] ≤ 1000000

SAMPLE INPUT
5
1 2 3 4 5

SAMPLE OUTPUT
-1
-1
6
24
60

Explanation

There are 5 integers 1,2,3,4 and 5.
For the first two indexes, since the number of elements is less than 3, so -1 is printed.
For the third index, the top 3 numbers are 3,2 and 1 whose product is 6.
For the fourth index, the top 3 numbers are 4,3, and 2 whose product is 24.
For the fifth index, the top 3 numbers are 5,4 and 3 whose product is 60.

Source: hackerearth | Difficulty: EASY
Tags: Data structures


Solutions:
from heapq import heappush, heappop

n = int(input())

line = input()
words = line.split()
a = [int(word) for word in words]

heap = []

for i in range(n):
	heappush(heap, -a[i])
	
	# print(heap)
	
	if len(heap) < 3:
		print((-1))
		continue
		
	first = heappop(heap)
	second = heappop(heap)
	third = heappop(heap)
	
	print((-1 * first * second * third))

	heappush(heap, first)
	heappush(heap, second)
	heappush(heap, third)

	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
num = eval(input())
Array = list(map(int, input().split()))
H1 = -1 
H2 = -1
H3 = -1

for Index in range(len(Array)):
	if H1 < Array[Index]:
		H3 = H2
		H2 = H1
		H1 = Array[Index]
		
	elif H2 < Array[Index]:
		H3 = H2
		H2 = Array[Index]
		
	elif H3 < Array[Index]:
		H3 = Array[Index]
		
	if Index < 2:
		print("-1")
	else:
		print(str(H1 * H2 * H3))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
num = eval(input())
Array = list(map(int, input().split()))
H1 = -1 
H2 = -1
H3 = -1

for Index in range(len(Array)):
	if H1 < Array[Index]:
		H3 = H2
		H2 = H1
		H1 = Array[Index]
		
	elif H2 < Array[Index]:
		H3 = H2
		H2 = Array[Index]
		
	elif H3 < Array[Index]:
		H3 = Array[Index]
		
	if Index < 2:
		print("-1")
	else:
		print(str(H1 * H2 * H3))


N = int(input())
l = [int(x) for x in input().split()]

if N==1:
	print(-1)
elif N==2:
	print(-1)
	print(-1)

else:
	print(-1)
	print(-1)
	x= l[0:3]
	x.sort()
	
	print(x[0]*x[1]*x[2])
	for i in range(3,N):
		#print x
		num = l[i]
		if num >x[2]:
			x[2],x[1],x[0] = num,x[2],x[1]
		elif num <=x[2] and num >x[1]:
			x[1],x[0] = num,x[1]
		elif num <=x[1] and num>x[0]:
			x[0] =num

		print(x[0]*x[1]*x[2])
		   
		
	
	
	
	


x, y, z = 0, 0, 0
n = int(input())
a = list(map(int, input().split()))
x = 0
print(-1)
if n > 1:
	y, z = sorted(a[:2])
	print(-1)
	for i in range(2, n):
		if a[i] > z:
			x = y
			y = z
			z = a[i]
		elif a[i] > y:
			x = y
			y = a[i]
		elif a[i] > x:
			x = a[i]
			
		print(x * y * z)
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
print 'Hello World!'
'''

def sort1(array,n):
	'''n0=int(array[0]);n1=int(array[1])
	n2=int(array[2])
	sort_array=array
	if n>n0:sort_array[0]=n;sort_array[2]=n0;sort_array[2]=n1
	elif n>n1:sort_array[0]=n0;sort_array[2]=n;sort_array[2]=n1
	elif n>n2:sort_array[0]=n0;sort_array[2]=n1;sort_array[2]=n
	return sort_array'''
	array.append(n)
	array.sort()
	array.pop(0)
	return array
def initialsort(a):
	for i in range(len(a)):
		a[i]=int(a[i])
	a.sort()
	return a
import sys
data=sys.stdin.readlines()
N=int(data[0])
arr=data[1].split()
print(-1)
print(-1)
a_initial=arr[0:3]
a=initialsort(a_initial)
ff=a[0]*a[1]*a[2]
print(ff)
for i in range(3,len(arr)):
	a=sort1(a,int(arr[i]))
	ff=a[0]*a[1]*a[2]
	print(ff)
	
	


from functools import reduce
in1 = eval(input())
in2 = input()
in2 = [int(i) for i in in2.split()]
list = list()
list.append(in2.pop(0))
list.append(in2.pop(0))
list.append(in2.pop(0))
list.sort()
mul = 0
print(-1,"\n",-1,"\n",reduce(lambda x,y:x*y,list))
for item in in2:
	if item > list[0]:
		list[0] = item
		list.sort()
		mul = reduce(lambda x,y:x*y,list)
	print(reduce(lambda x,y:x*y,list))


# your code goes here
 		
def func2(a):
	lar = []
	if(len(a)>2):
		for x in range(3):
			lar.append(a[x])
		
	for x in range(len(a)):
		lar.sort()
		if(x<2):
			print('-1')
		
		if(x == 2):
			print((lar[0]*lar[1]*lar[2]))
			
		if(x>2):
			if(lar[0]<a[x]):
				lar[0] = a[x]
				
			print((lar[0]*lar[1]*lar[2]))
		
			
 
t = int(input())
a = list(map(int,input().split()))
 	
func2(a)
 
 





n=eval(input())
a=list(map(int,input().split()))
m1=max(a[0],a[1])
if m1==a[0]:
	m2=a[1]
else:
	m2=a[0]
m3=0
ans=[-1,-1]
for i in range(2,n):
	if m1<a[i]:
		m3=m2
		m2=m1
		m1=a[i]
	elif m2<a[i]:
		m3=m2
		m2=a[i]
	elif m3<a[i]:
		m3=a[i]
	ans.append(m2*m1*m3)
for i in range(0,n):
	print(ans[i])


import heapq
n=eval(input())
l=[int(i) for i in input().split()]
h=[]
for i in range(0,n):
	val=-l[i]
	heapq.heappush(h,val)
	#print "1.",h
	if i<2:
		print(-1)
		#print "---------------------------------"
		continue
	a=heapq.heappop(h)
	#print "2.",h
	b=heapq.heappop(h)
	#print "3.",h
	c=heapq.heappop(h)
	#print "4.",h
	print(a*b*c*-1)
	heapq.heappush(h,a)
	#print "5.",h
	heapq.heappush(h,b)
	#print "6.",h
	heapq.heappush(h,c)
	#print "7.",h
	#print h
	


n = int(input())
arr = [int(w) for w in input().split()]
assert len(arr) == n

top = arr[:3]
top.sort()

prod = 1
for x in top:
	prod *= x

for i in range(len(top)-1):
	print(-1)
print(prod)

for x in arr[len(top):]:
    if x > top[0]:
	prod = (prod / top[0]) * x
	top[0] = x
	for i in range(1,len(top)):
	    if top[i-1] <= top[i]:
		break
	    top[i-1] = top[i]
	    top[i] = x
    print(prod)


n=int(input())
j=input().split()
i=1
for d in j:
	d=int(d)
	if i==1:
		x=d
		print("-1")
	elif i==2:
		if d>x:
			y=x
			x=d
		else:
			y=d
		print("-1")
	elif i==3:
		if d>y:
			if d>x:
				z=y
				y=x
				x=d
			else:
				z=y
				y=d
		else :
			z=d
		print(x*y*z)
	else:
		if d>z:
			if d>y:
				if d>x:
					z=y
					y=x
					x=d
				else:
					z=y
					y=d
			else :
				z=d
		print(x*y*z)
	i+=1            


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
from functools import reduce
length = int(input())
elements = list(map(int, input().split(' ')))

temp = []
if length <3:
	for i in range(0,length): 
		print(-1)
elif length == 3:
	print(reduce(lambda x, y: x*y, elements))
else:
	print(-1)
	print(-1)
	ini_prod =  reduce(lambda x, y: x*y, elements[0:3])
	print(ini_prod)
	temp = elements[0:3]
	temp.sort(reverse = True)

	for i in range(3,length):
		new_ele = elements[i]
		if new_ele >  temp[0] or new_ele >  temp[1] or new_ele >  temp[2] :
				if new_ele > temp[0]:
					temp.insert(0,new_ele)
				elif new_ele > temp[1]:
					temp.insert(1,new_ele)
				elif new_ele > temp[2]:
					temp.insert(2,new_ele)	
				
		
		print(temp[0]*temp[1]*temp[2])
		#temp = temp[0:3]
	


import heapq
n=eval(input())
heap=[]
listi=[int(i) for i in input().split()]
for i in range(n):
	heapq.heappush(heap,-listi[i])
	if len(heap)<3:
		print("-1")
		continue
	else:
		x=-(heapq.heappop(heap))
		y=-(heapq.heappop(heap))
		z=-(heapq.heappop(heap))
		heapq.heappush(heap,-x)
		heapq.heappush(heap,-y)
		heapq.heappush(heap,-z)
		x=x*y*z
		print(x)


# doesn't need heap(nlogn), linear sufficient O(n)
n=int(input())
a=list(map(int,input().split()))
x=0
y=0
z=0
for i in range(n):
	if a[i]>=x:
		x,y,z=a[i],x,y
	elif a[i]>=y:
		y,z=a[i],y
	elif a[i]>=z:
		z=a[i]
	if i<2:
		print(-1)
	else:
		print(x*y*z)


import heapq

n=eval(input())
a=list(map(int,input().split()))
minheap=[]
l=len(a)
for i in range(l):
	if len(minheap)<3:
		heapq.heappush(minheap,a[i])
	elif minheap[0]<a[i]:
		minheap[0]=a[i]
		heapq.heapify(minheap)

	if len(minheap)<3:
		print(-1)
	else:
		#print minheap[0],minheap[1],minheap[2]
		print(minheap[0]*minheap[1]*minheap[2])
		


import heapq

n=eval(input())
heap=[]
values=[int(x) for x in input().split()]
heapq.heappush(heap,-values[0])
heapq.heappush(heap,-values[1])
for i in range(0,n):
	if i==0 or i==1:
		print(-1)
	else:
		heapq.heappush(heap,-values[i])
		val1=-heapq.heappop(heap)
		val2=-heapq.heappop(heap)
		val3=-heapq.heappop(heap)
		print(val1*val2*val3)
		heapq.heappush(heap,-val1)
		heapq.heappush(heap,-val2)
		heapq.heappush(heap,-val3)
		#print heap


t=int(input())
l=list(map(int,input().split()))
n=[]
for i in range(0,t):
	n.append(l[i])
	if len(n)<3:
		print(-1)
	elif len(n)>3:
		x=n.index(min(n))
		n.pop(x)
		print(n[0]*n[1]*n[2])
	else:
		print(n[0]*n[1]*n[2])


from heapq import heappush, heappop


def find_three_biggest(numbers):
	h = []
	for i in range(len(numbers)):
		heappush(h, -numbers[i])
		if i < 2:
			yield -1
		else:
			a = heappop(h)
			b = heappop(h)
			c = heappop(h)
			yield -1 * a * b * c
			heappush(h, a)
			heappush(h, b)
			heappush(h, c)


def solve(numbers):
	for v in find_three_biggest(numbers):
		print(v)


def execute():
	n = int(input())
	numbers = list(map(int, input().split()))
	solve(numbers)

if __name__ == '__main__':
	execute()


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
print 'Hello World!'
'''
import sys
def sort1(array,n):
	'''n0=int(array[0]);n1=int(array[1])
	n2=int(array[2])
	sort_array=array
	if n>n0:sort_array[0]=n;sort_array[2]=n0;sort_array[2]=n1
	elif n>n1:sort_array[0]=n0;sort_array[2]=n;sort_array[2]=n1
	elif n>n2:sort_array[0]=n0;sort_array[2]=n1;sort_array[2]=n
	return sort_array'''
	array.append(n)
	array.sort()
	array.pop(0)
	return array
def initialsort(a):
	for i in range(len(a)):
		a[i]=int(a[i])
	a.sort()
	return a
data=sys.stdin.readlines()
N=int(data[0])
arr=data[1].split()
print(-1)
print(-1)
a_initial=arr[0:3]
a=initialsort(a_initial)
ff=a[0]*a[1]*a[2]
print(ff)
for i in range(3,len(arr)):
	a=sort1(a,int(arr[i]))
	ff=a[0]*a[1]*a[2]
	print(ff)
	
	


import heapq
n=eval(input())
lst=[]
lst=[-int(x) for x in input().split()]
#print lst
x=min(3,n)
for _ in range(1,x):
	print(-1)
heapq.heapify(lst[:3])
hep=lst[:2]
#print hep
for i in range(2,n):
	x=heapq.heappushpop(hep,lst[i])
#	print hep
	y=heapq.heappop(hep)
	z=heapq.heappop(hep)
#	print x,y,z
	print(abs(x*y*z))
	heapq.heappush(hep,x)
	heapq.heappush(hep,y)
	heapq.heappush(hep,z)
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
from functools import reduce
length = int(input())
elements = list(map(int, input().split(' ')))

temp = []
if length <3:
	for i in range(0,length): 
		print(-1)
elif length == 3:
	print(reduce(lambda x, y: x*y, elements))
else:
	print(-1)
	print(-1)
	ini_prod =  reduce(lambda x, y: x*y, elements[0:3])
	print(ini_prod)
	#temp.append(elements[0])
	#temp.append(elements[1])
	#temp.append(elements[2])
	temp = elements[0:3]
	
	
	temp.sort(reverse = True)

	for i in range(3,length):
		new_ele = elements[i]
		if new_ele >  temp[0] or new_ele >  temp[1] or new_ele >  temp[2] :
				if new_ele > temp[0]:
					temp.insert(0,new_ele)
				elif new_ele > temp[1]:
					temp.insert(1,new_ele)
				elif new_ele > temp[2]:
					temp.insert(2,new_ele)	
				
		#print new_arraytemp[0]
		#new_array.sort(reverse = True)
		#print new_array
		print(temp[0]*temp[1]*temp[2])
	


import heapq

n = input()
x_lst = []
lst = list(map(int , input().split()))
for i in range(len(lst)):
	if len(x_lst) >= 2:
		heapq.heappush(x_lst,lst[i])
		p = 1;
		if len(x_lst) > 3: 
			heapq.heappop(x_lst);
		for j in x_lst:
			p = p*j
		print(p)
	else:
		heapq.heappush(x_lst,lst[i])
		print(-1)


n = eval(input())
num = [int(i) for i in input().split()]
prods = [-1,-1]
giv = num[:3]
for i in range(3,n):
	pr = giv[0]*giv[1]*giv[2]
	prods+=[pr]
	nn = num[i]
	giv+=[nn]
	giv.sort()
	del giv[0]
pr = giv[0]*giv[1]*giv[2]
prods+=[pr]
for i in range(n):
	print(prods[i])


n = int(input())
arr = [int(x) for x in input().split()]
a=-2
b=-1
c=0
for i in range(n):
	if arr[i] > a :
		if arr[i] > b :
			if arr[i] > c :
				a=b
				b=c
				c=arr[i]
			else:
				a=b
				b=arr[i]
		else:
			a=arr[i]
	if i<2:
		print(-1)
	else:
		print(a*b*c)


def prod(xs):
	p = 1
	for x in xs:
		p *= x
	return p

def solve(xs):
	res = []
	biggests = []
	for x in xs:
		biggests.append(x)
		biggests.sort(reverse=True)
		while len(biggests) > 3: biggests.pop()
		res.append(prod(biggests) if len(biggests) == 3 else -1)
	return '\n'.join(str(x) for x in res)

if __name__ == '__main__':
	input()
	print(solve(list(map(int, input().split()))))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
N = eval(input())
A = list(map(int, input().split(" ")))
q= [0,0,0]

for i in A :
	if i >= q[2] :
		q[0]             = q[1]
		q[1]             = q[2]
		q[2]             = i
	elif i < q[2] and i >= q[1] : 
		q[0]             = q[1]
		q[1]             = i
	elif i < q[1] and i > q[0] :
		q[0] = i
	
	product = q[0] * q[1] * q[2]
	
	if product <= 0 :
		print((-1))
	else :
		print(product)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
# n = int(raw_input())

# listOfNumbers = list(map(int,raw_input().split()))

# for i in xrange(n):
heap = [-1]*3
heap_size = 0

n= int(input())
arr = list(map(int,input().split()))

def insertHeap(i):
	if heap[0]<i:
		heap[0] = i
	elif heap[1]<i:
		heap[1] = i
	elif heap[2]<i:
		heap[2]=i
	heap.sort()
		
def prodHeap():
	return heap[0]*heap[1]*heap[2]
# print n
for i in range(n):
	if i==0 or i==1:
		heap[i] = arr[i]
		print(-1)
	elif i==2:
		heap[i] = arr[i]
		heap.sort()
		print(prodHeap())
	else:
		insertHeap(arr[i])
		print(prodHeap())
	# print heap

		
	

	
	
	
	
	
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n = int(input())
l = []
l.append(0)
l.append(0)
l.append(0)
inp = input().split(' ')
inp = list(map(int,inp))
for j in range(n):
	x = inp[j]
	#print x
	c = 0
	for i in range(3):
		if l[i]<x:
			l.append(x)
			c = 1
			break
	#print l
	l.sort()
	#print l
	if c==1:
		l = l[1:4]
	#print l
	if l[0]*l[1]*l[2] == 0:
		print(-1)
	else:
		print(l[0]*l[1]*l[2])


x=eval(input())
a=[]
y=list(map(int,input().split()))
print("-1")
print("-1")
a.append(y[0])
a.append(y[1])
for i in range(2,x):
	a.append(y[i])
	a.sort()
	if(len(a)>3):
		a.pop(0)
	print(a[0]*a[1]*a[2])



n = int(input())
elms = [int(i) for i in input().split()]

tl, sl, lg = sorted(elms[:3])

res = [-1, -1, tl * sl * lg]

for i in range(3, n):
	el = elms[i]
	if el >= lg:
		tl = sl
		sl = lg
		lg = el
	elif el >= sl:
		tl = sl
		sl = el
	elif el >= tl:
		tl = el

	res.append(lg * sl * tl)

print("\n".join(str(i) for i in res))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
N = int(input())
arr = [int(i) for i in input().split()]
l = []
for i in range(N):
	if i < 2:
		print(-1)
	elif i == 2:
		l = [arr[0], arr[1], arr[2]]
		l.sort()
		
		print(l[0] * l[1] * l[2])
	else:
		if arr[i] >= l[2]:
			l[0] = l[1]
			l[1] = l[2]
			l[2] = arr[i]
		elif arr[i] >= l[1]:
			l[0] = l[1]
			l[1] = arr[i]
		elif arr[i] >= l[0]:
			l[0] = arr[i]
	
		print(l[0] * l[1] * l[2])
			


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
from functools import reduce
length = int(input())
elements = list(map(int, input().split(' ')))

temp = []
if length <3:
	for i in range(0,length): 
		print(-1)
elif length == 3:
	print(reduce(lambda x, y: x*y, elements))
else:
	print(-1)
	print(-1)
	ini_prod =  reduce(lambda x, y: x*y, elements[0:3])
	print(ini_prod)
	temp = elements[0:3]
	temp.sort(reverse = True)

	for i in range(3,length):
		new_ele = elements[i]
		if new_ele >  temp[0] or new_ele >  temp[1] or new_ele >  temp[2] :
				if new_ele > temp[0]:
					temp.insert(0,new_ele)
				elif new_ele > temp[1]:
					temp.insert(1,new_ele)
				elif new_ele > temp[2]:
					temp.insert(2,new_ele)	
				
		
		print(temp[0]*temp[1]*temp[2])
		if len(temp) == 4 :
			del temp[3]
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
from functools import reduce
length = int(input())
elements = list(map(int, input().split(' ')))

temp = []
if length <3:
	for i in range(0,length): 
		print(-1)
elif length == 3:
	print(reduce(lambda x, y: x*y, elements))
else:
	print(-1)
	print(-1)
	ini_prod =  reduce(lambda x, y: x*y, elements[0:3])
	print(ini_prod)
	temp = elements[0:3]
	temp.sort(reverse = True)

	for i in range(3,length):
		new_ele = elements[i]
		if new_ele >  temp[0] or new_ele >  temp[1] or new_ele >  temp[2] :
				if new_ele > temp[0]:
					temp.insert(0,new_ele)
				elif new_ele > temp[1]:
					temp.insert(1,new_ele)
				elif new_ele > temp[2]:
					temp.insert(2,new_ele)	
				
		
		print(temp[0]*temp[1]*temp[2])
		temp = temp[0:3]
	


import sys, heapq

ff = sys.stdin
N = int(ff.readline())
number_list = [int(x) for x in ff.readline().strip().split()]
max_3 = None
for i in range(N) :
	if i < 2 :
		print((-1))
	else :
		if i == 2 :
			max_3 = number_list[0:3]
			print((max_3[0] * max_3[1] * max_3[2]))
		else :
			max_3.append(number_list[i])
			x,y,z = heapq.nlargest(3, max_3)
			print((x * y * z))
			max_3 = [x, y , z]