Given an array arr of size n, the task is to find the maximum triplet product in the array.
Example 1:
Input:
n = 4
arr[] = {1, 2, 3, 5}
Output:
30
Explanation:
5*3*2 gives 30. This is the maximum possible
triplet product in the array.
Example 2:
Input:
n = 7
arr[] = {-3, -5, 1, 0, 8, 3, -2} 
Output:
120
Explanation: 
-3*-5*8 gives 120. This is the maximum possible triplet product in the array.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxTripletProduct() which takes an integer n and an array arr and returns the maximum triplet product in the array.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
3 ≤ N ≤ 5*10^{5}
-10^{6} ≤ A[i] ≤ 10^{6}

Difficulty: MEDIUM
Tags: Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def maxTripletProduct (self, arr,  n): 

        #Complete the function



Solutions:
class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		n = len(arr)
		product1 = arr[n - 1] * arr[n - 2] * arr[n - 3]
		product2 = arr[0] * arr[1] * arr[n - 1]
		return max(product1, product2)


class Solution:

	def maxTripletProduct(self, arr, n):
		x = sorted(arr)
		neg = 0
		for i in x:
			if i < 0:
				neg += 1
		if neg >= 2:
			return max(x[0] * x[1] * x[-1], x[-1] * x[-2] * x[-3])
		else:
			return x[-1] * x[-2] * x[-3]


class Solution:

	def maxTripletProduct(self, arr, n):
		firstMax = float('-inf')
		secondMax = float('-inf')
		thirdMax = float('-inf')
		firstMin = float('inf')
		secondMin = float('inf')
		for i in range(0, n):
			if arr[i] > firstMax:
				thirdMax = secondMax
				secondMax = firstMax
				firstMax = arr[i]
			elif arr[i] > secondMax:
				thirdMax = secondMax
				secondMax = arr[i]
			elif arr[i] > thirdMax:
				thirdMax = arr[i]
			if arr[i] < firstMin:
				secondMin = firstMin
				firstMin = arr[i]
			elif arr[i] < secondMin:
				secondMin = arr[i]
		return max(firstMax * secondMax * thirdMax, firstMin * secondMin * firstMax)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		product = arr[n - 1] * arr[n - 2] * arr[n - 3]
		product1 = arr[0] * arr[1] * arr[n - 1]
		return max(product, product1)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		p1 = arr[0] * arr[1] * arr[n - 1]
		p2 = arr[n - 1] * arr[n - 2] * arr[n - 3]
		return max(p1, p2)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		a = arr[0] * arr[1] * arr[2]
		b = arr[-1] * arr[-2] * arr[-3]
		c = arr[-1] * arr[0] * arr[1]
		d = arr[-1] * arr[-2] * arr[0]
		return max(a, b, c, d)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr = sorted(arr)
		max1 = arr[n - 1] * arr[n - 2] * arr[n - 3]
		max2 = arr[n - 1] * arr[0] * arr[1]
		if max1 > max2:
			return max1
		return max2


class Solution:

	def maxTripletProduct(self, nums, n):
		arr.sort(reverse=True)
		if nums[0] < 0:
			return nums[0] * nums[1] * nums[2]
		else:
			a = nums[0] * nums[-1] * nums[-2]
			b = nums[0] * nums[1] * nums[2]
			return max(a, b)


class Solution:

	def maxTripletProduct(self, arr, n):
		min1 = min2 = float('inf')
		max1 = max2 = max3 = -float('inf')
		for num in arr:
			if num <= min2:
				if num <= min1:
					min2 = min1
					min1 = num
				else:
					min2 = num
			if num >= max3:
				if num >= max2:
					if num >= max1:
						(max2, max3) = (max1, max2)
						max1 = num
					else:
						max3 = max2
						max2 = num
				else:
					max3 = num
		return max(max1 * max2 * max3, min1 * min2 * max1)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr1 = arr
		(max1, max2, max3) = (arr1[0], -sys.maxsize, -sys.maxsize)
		for i in range(1, n):
			if arr1[i] > max1:
				max1 = arr1[i]
		arr1.remove(max1)
		for i in range(len(arr1)):
			if arr1[i] > max2 and arr1[i] <= max1:
				max2 = arr1[i]
		arr1.remove(max2)
		for i in range(len(arr1)):
			if arr1[i] > max3 and arr1[i] <= max2:
				max3 = arr1[i]
		arr1.remove(max3)
		arr1.append(max1)
		arr1.append(max2)
		arr1.append(max3)
		(min1, min2) = (sys.maxsize, sys.maxsize)
		for i in range(len(arr1)):
			if arr1[i] < min1:
				min1 = arr1[i]
		arr1.remove(min1)
		for i in range(len(arr1)):
			if arr1[i] < min2 and arr1[i] >= min1:
				min2 = arr1[i]
		return max(max1 * min1 * min2, max1 * max2 * max3)


class Solution:

	def maxTripletProduct(self, arr, n):
		min1 = min2 = float('inf')
		m1 = m2 = m3 = -float('inf')
		for i in arr:
			if i <= min1:
				if i <= min2:
					min1 = min2
					min2 = i
				else:
					min1 = i
			elif i <= min2:
				min2 = i
			if i >= m1:
				if i >= m2:
					if i >= m3:
						m1 = m2
						m2 = m3
						m3 = i
					else:
						m1 = m2
						m2 = i
				else:
					m1 = i
		return max(m1 * m2 * m3, max(m1, m2, m3) * min1 * min2)


class Solution:

	def maxTripletProduct(self, arr, n):
		new = sorted(arr)
		return max(new[0] * new[1] * new[-1], new[-1] * new[-2] * new[-3])


def per(i, j, pos, neg, c, p):
	if c == 3:
		return p
	m = -100000000.0
	if i < len(pos):
		m = max(m, per(i + 1, j, pos, neg, c + 1, p * pos[i]))
	if j < len(neg):
		m = max(m, per(i, j + 1, pos, neg, c + 1, p * neg[j]))
	return m

class Solution:

	def maxTripletProduct(self, arr, n):
		neg = [100000000.0, 100000000.0, 100000000.0]
		pos = [-100000000.0, -100000000.0, -100000000.0]
		for i in arr:
			if i >= 0:
				if i > pos[0]:
					pos[2] = pos[1]
					pos[1] = pos[0]
					pos[0] = i
				elif i > pos[1]:
					pos[2] = pos[1]
					pos[1] = i
				elif i > pos[2]:
					pos[2] = i
			elif i < neg[0]:
				neg[2] = neg[1]
				neg[1] = neg[0]
				neg[0] = i
			elif i < neg[1]:
				neg[2] = neg[1]
				neg[1] = i
			elif i < neg[2]:
				neg[2] = i
		while neg and neg[-1] == 100000000.0:
			neg.pop()
		while pos and pos[-1] == -100000000.0:
			pos.pop()
		if pos == []:
			pos = [-100000000.0, -100000000.0, -100000000.0]
			for i in arr:
				if i > pos[0]:
					pos[2] = pos[1]
					pos[1] = pos[0]
					pos[0] = i
				elif i > pos[1]:
					pos[2] = pos[1]
					pos[1] = i
				elif i > pos[2]:
					pos[2] = i
			return pos[0] * pos[1] * pos[2]
		return per(0, 0, pos, neg, 0, 1)


class Solution:

	def maxTripletProduct(self, arr, n):
		if n < 3:
			return -1
		arr.sort()
		max_product = max(arr[n - 1] * arr[n - 2] * arr[n - 3], arr[0] * arr[1] * arr[n - 1])
		return max_product


class Solution:

	def maxTripletProduct(self, A, n):
		A.sort()
		if A[n - 1] < 0:
			return A[n - 1] * A[n - 2] * A[n - 3]
		elif A[n - 2] < 0 or A[n - 3] < 0:
			return A[n - 1] * A[0] * A[1]
		elif A[n - 1] * A[n - 2] * A[n - 3] > A[0] * A[1] * A[n - 1]:
			return A[n - 1] * A[n - 2] * A[n - 3]
		else:
			return A[0] * A[1] * A[n - 1]


class Solution:

	def maxTripletProduct(self, arr, n):
		(x, y, z) = (0, 0, 0)
		arr.sort()
		x = arr[n - 3] * arr[n - 2] * arr[n - 1]
		y = arr[0] * arr[1]
		z = y * max(arr)
		return max(x, z)


class Solution:

	def maxTripletProduct(self, arr, n):
		if n < 3:
			return -1
		max1 = max2 = max3 = float('-inf')
		min1 = min2 = float('inf')
		for i in range(n):
			if arr[i] > max1:
				max3 = max2
				max2 = max1
				max1 = arr[i]
			elif arr[i] > max2:
				max3 = max2
				max2 = arr[i]
			elif arr[i] > max3:
				max3 = arr[i]
			if arr[i] < min1:
				min2 = min1
				min1 = arr[i]
			elif arr[i] < min2:
				min2 = arr[i]
		return max(max1 * max2 * max3, max1 * min1 * min2)


class Solution:

	def maxTripletProduct(self, arr, n):
		if len(arr) == 3:
			return arr[0] * arr[1] * arr[2]
		low = -9999999
		high = 9999999
		pos = [low, low, low]
		neg = [high, high]
		for i in arr:
			if i > pos[0]:
				pos = [i, pos[0], pos[1]]
			elif i > pos[1]:
				(pos[1], pos[2]) = (i, pos[1])
			elif i > pos[2]:
				pos[2] = i
			if i < neg[0]:
				neg = [i, neg[0]]
			elif i < neg[1]:
				neg[1] = i
		return max(pos[0] * neg[0] * neg[1], pos[0] * pos[1] * pos[2])


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		top = arr[-1] * arr[-2] * arr[-3]
		bottom = arr[0] * arr[1] * arr[-1]
		return max(top, bottom)


class Solution:

	def maxTripletProduct(self, arr, n):
		maxA = -sys.maxsize - 1
		maxB = -sys.maxsize - 1
		maxC = -sys.maxsize - 1
		minA = sys.maxsize
		minB = sys.maxsize
		for i in range(n):
			if arr[i] > maxA:
				maxC = maxB
				maxB = maxA
				maxA = arr[i]
			elif arr[i] > maxB:
				maxC = maxB
				maxB = arr[i]
			elif arr[i] > maxC:
				maxC = arr[i]
			if arr[i] < minA:
				minB = minA
				minA = arr[i]
			elif arr[i] < minB:
				minB = arr[i]
		return max(minA * minB * maxA, maxA * maxB * maxC)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		prod1 = arr[n - 1] * arr[n - 2] * arr[n - 3]
		prod2 = arr[0] * arr[1] * arr[n - 1]
		return prod1 if prod1 > prod2 else prod2


class Solution:

	def maxTripletProduct(self, a, n):
		max2 = -9999999
		max1 = a[0]
		max3 = -99999999
		for i in range(1, n):
			if a[i] >= max1:
				max3 = max2
				max2 = max1
				max1 = a[i]
			elif a[i] < max1 and a[i] >= max2:
				max3 = max2
				max2 = a[i]
			elif a[i] < max1 and a[i] < max2 and (a[i] > max3):
				max3 = a[i]
		ans1 = max1 * max2 * max3
		maxneg1 = 0
		maxneg2 = 0
		for i in range(n):
			if a[i] < 0 and a[i] <= maxneg1:
				maxneg2 = maxneg1
				maxneg1 = a[i]
			elif a[i] < 0 and a[i] > maxneg1 and (a[i] < maxneg2):
				maxneg2 = a[i]
		if maxneg2 != 0:
			ans2 = max1 * maxneg1 * maxneg2
		else:
			ans2 = ans1
		return max(ans1, ans2)


import heapq

class Solution:

	def maxTripletProduct(self, arr, n):
		min_heap = arr[0:3]
		max_heap = [-arr[0], -arr[1]]
		heapq.heapify(min_heap)
		heapq.heapify(max_heap)
		for i in range(3, n):
			if arr[i] > min_heap[0]:
				heapq.heappop(min_heap)
				min_heap.append(arr[i])
				heapq.heapify(min_heap)
		for i in range(2, n):
			if arr[i] < -max_heap[0]:
				heapq.heappop(max_heap)
				max_heap.append(-arr[i])
				heapq.heapify(max_heap)
		min_heap.sort()
		first_max = min_heap[2]
		return max(min_heap[0] * min_heap[1] * min_heap[2], first_max * -max_heap[0] * -max_heap[1])


import numpy as np

class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		count = 0
		return max(np.product(arr[:3]), np.product(arr[:2]) * arr[-1], np.product(arr[-3:]))


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		x = arr[-3] * arr[-2] * arr[-1]
		y = arr[0] * arr[1] * arr[-1]
		if x > y:
			return x
		else:
			return y


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		max1 = arr[-1]
		max2 = arr[-2]
		max3 = arr[-3]
		min1 = arr[0]
		min2 = arr[1]
		return max(max1 * max2 * max3, min1 * min2 * max1)


class Solution:

	def maxTripletProduct(self, arr, n):
		max1 = max2 = max3 = -float('inf')
		min1 = min2 = float('inf')
		arr.sort()
		for element in arr:
			if element > max1:
				max3 = max2
				max2 = max1
				max1 = element
			elif element > max2:
				max3 = max2
				max2 = element
			elif element > max3:
				max3 = element
			if element < min1:
				min2 = min1
				min1 = element
			elif element < min2:
				min2 = element
		return max(max1 * max2 * max3, min1 * min2 * max1)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		neg = 0
		for i in arr:
			if i < 0:
				neg += 1
		if neg == n:
			return arr[n - 1] * arr[n - 2] * arr[n - 3]
		else:
			negprod = arr[0] * arr[1]
			posprod = arr[n - 2] * arr[n - 3]
			if negprod > posprod:
				return negprod * arr[n - 1]
			else:
				return posprod * arr[n - 1]


class Solution:

	def maxTripletProduct(self, arr, n):
		x = arr.sort()
		x1 = arr[0] * arr[1] * arr[-1]
		x2 = arr[-1] * arr[-2] * arr[-3]
		return max(x1, x2)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		a = arr[0] * arr[1] * arr[-1]
		b = arr[-1] * arr[-2] * arr[-3]
		if len(arr) == 1:
			return arr[0]
		elif len(arr) == 2:
			return arr[1] * arr[0]
		else:
			return max(a, b)


class Solution:

	def maxTripletProduct(self, arr, n):
		p1 = p2 = p3 = -1000000000
		n1 = n2 = 1000000000
		for i in range(len(arr)):
			if arr[i] >= p1:
				(p3, p2, p1) = (p2, p1, arr[i])
			elif arr[i] >= p2:
				(p3, p2) = (p2, arr[i])
			elif arr[i] >= p3:
				p3 = arr[i]
			if arr[i] <= n1:
				(n2, n1) = (n1, arr[i])
			elif arr[i] <= n2:
				n2 = arr[i]
		return max(p1 * p2 * p3, p1 * n1 * n2)


class Solution:

	def maxTripletProduct(self, arr, n):
		if n == 3:
			return arr[0] * arr[1] * arr[2]
		elif n == 4:
			l = []
			l.extend(arr)
			a = min(l)
			l.remove(a)
			b = min(l)
			l.remove(b)
			c = max(arr)
			arr.remove(c)
			d = max(arr)
			arr.remove(d)
			e = max(arr)
			arr.remove(e)
			return max(a * b * c, c * d * e)
		elif n >= 5:
			a = max(arr)
			arr.remove(a)
			b = max(arr)
			arr.remove(b)
			c = max(arr)
			arr.remove(c)
			d = min(arr)
			arr.remove(d)
			e = min(arr)
			return max(a * b * c, a * e * d)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		n1 = arr[n - 1] * arr[n - 2] * arr[n - 3]
		if arr[0] < 0 and arr[1] < 0:
			m = arr[0] * arr[1] * arr[n - 1]
			return max(m, n1)
		return n1


class Solution:

	def maxTripletProduct(self, arr, n):

		def bubble(arr):
			for i in range(len(arr) - 1):
				if arr[i] > arr[i + 1]:
					(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])

		def bubble_r(arr):
			for i in range(len(arr) - 1, 0, -1):
				if arr[i] < arr[i - 1]:
					(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
		bubble(arr)
		bubble(arr)
		bubble(arr)
		bubble_r(arr)
		bubble_r(arr)
		p1 = arr[-1] * arr[-2] * arr[-3]
		p2 = arr[0] * arr[1] * arr[-1]
		return max(p1, p2)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		m = max(arr[0] * arr[1] * arr[n - 1], arr[0] * arr[n - 2] * arr[n - 1])
		m = max(m, arr[n - 3] * arr[n - 2] * arr[n - 1])
		return m


class Solution:

	def maxTripletProduct(self, arr, n):
		positve_product = 1
		negative_product = 1
		neg_pos_product = 1
		arr.sort()
		positive_product = arr[n - 1] * arr[n - 2] * arr[n - 3]
		negative_product = arr[0] * arr[1]
		neg_pos_product = negative_product * arr[n - 1]
		if positive_product > neg_pos_product:
			return positive_product
		else:
			return neg_pos_product


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		k = arr[-1] * arr[-2] * arr[-3]
		if max(arr) < 0:
			return k
		elif arr[0] * arr[1] > arr[-2] * arr[-3]:
			return arr[0] * arr[1] * arr[-1]
		else:
			return k


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		maxProduct = arr[n - 1] * arr[n - 2] * arr[n - 3]
		temp1 = arr[0] * arr[1] * arr[n - 1]
		temp2 = arr[n - 1] * arr[n - 2] * arr[0]
		if temp1 > maxProduct:
			maxProduct = temp1
		if temp2 > maxProduct:
			maxProduct = temp2
		return maxProduct


class Solution:

	def maxTripletProduct(self, arr, n):
		sortedArr = sorted(arr)
		if sortedArr[n - 1] < 0:
			return sortedArr[n - 1] * sortedArr[n - 2] * sortedArr[n - 3]
		elif sortedArr[0] * sortedArr[1] > sortedArr[n - 2] * sortedArr[n - 3]:
			return sortedArr[n - 1] * sortedArr[0] * sortedArr[1]
		else:
			return sortedArr[n - 1] * sortedArr[n - 2] * sortedArr[n - 3]


class Solution:

	def maxTripletProduct(self, l, n):
		maxa = float('-inf')
		maxb = float('-inf')
		maxc = float('-inf')
		mina = float('inf')
		minb = float('inf')
		for i in l:
			if i > maxa:
				maxc = maxb
				maxb = maxa
				maxa = i
			elif i > maxb:
				maxc = maxb
				maxb = i
			elif i > maxc:
				maxc = i
			if i < mina:
				minb = mina
				mina = i
			elif i < minb:
				minb = i
		return max(maxa * maxb * maxc, maxa * mina * minb)


class Solution:

	def maxTripletProduct(self, arr, n):
		first = -10 ** 7
		second = -10 ** 7
		third = -10 ** 7
		fl = 10 ** 7
		sl = 10 ** 7
		for i in range(n):
			if arr[i] < fl:
				sl = fl
				fl = arr[i]
			elif arr[i] < sl:
				sl = arr[i]
			if arr[i] > first:
				third = second
				second = first
				first = arr[i]
			elif arr[i] > second:
				third = second
				second = arr[i]
			elif arr[i] > third:
				third = arr[i]
		ans = max(first * second * third, fl * sl * first)
		return ans


class Solution:

	def maxTripletProduct(self, arr, n):
		(F1, F2, F3) = (float('-inf'), float('-inf'), float('-inf'))
		(f1, f2) = (float('inf'), float('inf'))
		for i in range(n):
			if arr[i] >= F1:
				F3 = F2
				F2 = F1
				F1 = arr[i]
			elif arr[i] >= F2:
				F3 = F2
				F2 = arr[i]
			elif arr[i] >= F3:
				F3 = arr[i]
			if arr[i] <= f1:
				f2 = f1
				f1 = arr[i]
			elif arr[i] <= f2:
				f2 = arr[i]
		return max(F1 * F2 * F3, f1 * f2 * F1)


class Solution:

	def maxTripletProduct(self, arr, n):
		(m1, m2, m3) = (-sys.maxsize - 1, -sys.maxsize - 1, -sys.maxsize - 1)
		(n1, n2) = (0, 0)
		for i in range(0, n):
			if arr[i] >= m1:
				m3 = m2
				m2 = m1
				m1 = arr[i]
			elif arr[i] >= m2:
				m3 = m2
				m2 = arr[i]
			elif arr[i] >= m3:
				m3 = arr[i]
			if arr[i] < 0:
				if n1 >= arr[i]:
					n2 = n1
					n1 = arr[i]
				elif n2 >= arr[i]:
					n2 = arr[i]
		if m1 > 0:
			if n2 != 0:
				return max(n1 * n2, m2 * m3) * m1
		return m1 * m2 * m3


class Solution:

	def maxTripletProduct(self, arr, n):
		_1 = max(arr)
		arr.remove(_1)
		_2 = max(arr)
		arr.remove(_2)
		_3 = max(arr)
		arr.remove(_3)
		arr.extend([_1, _2, _3])
		__1 = min(arr)
		arr.remove(__1)
		__2 = min(arr)
		arr.remove(__2)
		return max(_1 * _2 * _3, __1 * __2 * _1)


class Solution:

	def maxTripletProduct(self, arr, n):
		mn1 = mn2 = float('inf')
		mx1 = mx2 = mx3 = -float('inf')
		for i in arr:
			if i <= mn2:
				if i <= mn1:
					mn2 = mn1
					mn1 = i
				else:
					mn2 = i
			if i >= mx3:
				if i >= mx2:
					if i >= mx1:
						(mx2, mx3) = (mx1, mx2)
						mx1 = i
					else:
						mx3 = mx2
						mx2 = i
				else:
					mx3 = i
		return max(mx1 * mx2 * mx3, mn1 * mn2 * mx1)


class Solution:

	def maxTripletProduct(self, l, n):
		l.sort()
		product_1 = l[n - 1] * l[n - 2] * l[n - 3]
		product_2 = l[0] * l[1] * l[n - 1]
		return max(product_1, product_2)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		a1 = arr[0] * arr[1]
		a2 = arr[-2] * arr[-3]
		return max(arr[-1] * a1, arr[-1] * a2)


class Solution:

	def maxTripletProduct(self, a, n):
		a.sort()
		d = a[0] * a[1] * a[-1]
		e = a[-1] * a[-2] * a[-3]
		return max(d, e)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		k = arr[-1] * arr[-2] * arr[-3]
		k2 = arr[0] * arr[1] * arr[-1]
		return max(k, k2)


class Solution:

	def maxTripletProduct(self, arr, n):
		arr.sort()
		first_min = arr[0]
		second_min = arr[1]
		first_max = arr[-1]
		second_max = arr[-2]
		third_max = arr[-3]
		ans1 = first_min * second_min * first_max
		ans2 = first_max * second_max * third_max
		if ans1 < ans2:
			return ans2
		else:
			return ans1


import heapq

class Solution:

	def maxTripletProduct(self, arr, n):
		min_heap = Heap(arr.copy(), 'min')
		max_heap = Heap(arr.copy(), 'max')
		min_heap.buildHeap()
		max_heap.buildHeap()
		min1 = min_heap.remove()
		negmul = 0
		if min1 < 0:
			min2 = min_heap.remove()
			negmul = min1 * min2
		max1 = max_heap.remove()
		max2 = max_heap.remove()
		max3 = max_heap.remove()
		return max(negmul * max1, max1 * max2 * max3)

class Heap:

	def __init__(self, arr, heap_type='min'):
		self.arr = arr
		self.heap_type = heap_type

	def buildHeap(self):
		for i in range(len(self.arr) // 2 - 1, -1, -1):
			self.heapify(i, self.heap_type)

	def insert(self, val):
		self.arr.append(val)
		self.buildHeap()

	def remove(self):
		if len(self.arr) == 0:
			return None
		(self.arr[0], self.arr[-1]) = (self.arr[-1], self.arr[0])
		temp = self.arr.pop()
		self.heapify(0, self.heap_type)
		return temp

	def heapify(self, i, heap_type):
		if heap_type == 'min':
			self.minHeapify(i)
		else:
			self.maxHeapify(i)

	def minHeapify(self, i):
		currmin = i
		left = 2 * i + 1
		right = 2 * i + 2
		if left < len(self.arr) and self.arr[currmin] > self.arr[left]:
			currmin = left
		if right < len(self.arr) and self.arr[currmin] > self.arr[right]:
			currmin = right
		if currmin != i:
			(self.arr[i], self.arr[currmin]) = (self.arr[currmin], self.arr[i])
			self.minHeapify(currmin)

	def maxHeapify(self, i):
		currmax = i
		left = 2 * i + 1
		right = 2 * i + 2
		if left < len(self.arr) and self.arr[currmax] < self.arr[left]:
			currmax = left
		if right < len(self.arr) and self.arr[currmax] < self.arr[right]:
			currmax = right
		if currmax != i:
			(self.arr[i], self.arr[currmax]) = (self.arr[currmax], self.arr[i])
			self.maxHeapify(currmax)

	def peek(self):
		if len(self.arr) == 0:
			return None
		return self.arr[0]

	def printHeap(self):
		print(self.arr)


class Solution:

	def maxTripletProduct(self, arr, n):
		a = sorted(arr)
		a1 = a[0]
		a2 = a[1]
		a3 = a[-1]
		a4 = a[-2]
		a5 = a[-3]
		b1 = a1 * a2 * a3
		b2 = a5 * a4 * a3
		if b1 > b2:
			return b1
		else:
			return b2


import heapq

class Solution:

	def maxTripletProduct(self, arr, n):
		temp = arr.copy()
		neg1 = min(temp)
		if neg1 < 0:
			temp.remove(neg1)
			neg2 = min(temp)
			temp.remove(neg2)
		temp = arr
		pos1 = max(temp)
		temp.remove(pos1)
		pos2 = max(temp)
		temp.remove(pos2)
		pos3 = max(temp)
		b = pos1 * pos2 * pos3
		if neg1 < 0 and neg2 < 0:
			a = neg1 * neg2 * pos1
			if a > b:
				return a
			return b
		else:
			return b


class Solution:

	def maxTripletProduct(self, arr, n):
		if n > 5:
			extr_arr = [0, 0, 0, 0, 0, 0]
			for i in range(0, 3):
				for j in range(i, n):
					if arr[j] < arr[i]:
						(arr[i], arr[j]) = (arr[j], arr[i])
			for i in range(0, 3):
				for j in range(i, n):
					if arr[n - j - 1] > arr[n - i - 1]:
						(arr[n - i - 1], arr[n - j - 1]) = (arr[n - j - 1], arr[n - i - 1])
			extr_arr = [arr[0], arr[1], arr[2], arr[n - 3], arr[n - 2], arr[n - 1]]
			max = extr_arr[0] * extr_arr[1] * extr_arr[2]
			for i in range(0, 6):
				for j in range(i + 1, 6):
					for k in range(j + 1, 6):
						if max < extr_arr[i] * extr_arr[j] * extr_arr[k]:
							max = extr_arr[i] * extr_arr[j] * extr_arr[k]
			return max
		if n < 6:
			max = arr[0] * arr[1] * arr[2]
			for i in range(0, n):
				for j in range(i + 1, n):
					for k in range(j + 1, n):
						if max < arr[i] * arr[j] * arr[k]:
							max = arr[i] * arr[j] * arr[k]
			return max