Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have the same width and the width is 1 unit, there will be N bars height of each bar will be given by the array arr.
Example 1:
Input:
N = 7
arr[] = {6,2,5,4,5,1,6}
Output: 12
Explanation: In this example the largest area would be 12 of height 4 and width 3. We can achieve this 
area by choosing 3rd, 4th and 5th bars.
Example 2:
Input:
N = 8
arr[] = {7 2 8 9 1 3 6 5}
Output: 16
Explanation: Maximum size of the histogram 
will be 8  and there will be 2 consecutive 
histogram. And hence the area of the 
histogram will be 8x2 = 16.
Your Task:
The task is to complete the function getMaxArea() which takes the array arr[] and its size N as inputs and finds the largest rectangular area possible and returns the answer.
Expected Time Complxity : O(N)
Expected Auxilliary Space : O(N)
Constraints:
1 ≤ N ≤ 10^{6}
0 ≤ arr[i] ≤ 10^{12}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Data structures

Starter code: #User function Template for python3





class Solution:

    

    #Function to find largest rectangular area possible in a given histogram.

    def getMaxArea(self,histogram):

        #code here

Solutions:
class Solution:

	def getMaxArea(self, histogram):
		stack = []
		maxarea = 0
		for (i, h) in enumerate(histogram):
			start = i
			while stack and stack[-1][1] > h:
				(index, height) = stack.pop()
				maxarea = max(maxarea, height * (i - index))
				start = index
			stack.append([start, h])
		for (i, h) in stack:
			maxarea = max(maxarea, (len(histogram) - i) * h)
		return maxarea


class Solution:

	def getMaxArea(self, histogram):
		stack = []
		stack2 = []
		right = []
		left = []
		n = len(histogram)
		for i in range(n):
			if not stack:
				left.append(-1)
			elif stack[-1][0] < histogram[i]:
				left.append(stack[-1][1])
			elif stack[-1][0] >= histogram[i]:
				while stack and stack[-1][0] >= histogram[i]:
					stack.pop()
				if len(stack) == 0:
					left.append(-1)
				else:
					left.append(stack[-1][1])
			stack.append([histogram[i], i])
		for i in range(n - 1, -1, -1):
			if not stack2:
				right.append(n)
			elif stack2[-1][0] < histogram[i]:
				right.append(stack2[-1][1])
			elif stack2[-1][0] >= histogram[i]:
				while stack2 and stack2[-1][0] >= histogram[i]:
					stack2.pop()
				if len(stack2) == 0:
					right.append(n)
				else:
					right.append(stack2[-1][1])
			stack2.append([histogram[i], i])
		realright = []
		while right:
			realright.append(right.pop())
		ans = []
		for i in range(n):
			ans.append(histogram[i] * (realright[i] - left[i] - 1))
		return max(ans)


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		arr = histogram
		st = []
		nsl = []
		nsr = []
		for i in range(n):
			flag = True
			while len(st) != 0:
				if st[-1][0] >= arr[i]:
					st.pop()
				else:
					nsl.append(st[-1][1])
					flag = False
					break
			if flag:
				nsl.append(-1)
			st.append((arr[i], i))
		st.clear()
		for j in range(n - 1, -1, -1):
			flag = True
			while len(st) != 0:
				if st[-1][0] >= arr[j]:
					st.pop()
				else:
					nsr.append(st[-1][1])
					flag = False
					break
			if flag:
				nsr.append(-1)
			st.append((arr[j], j))
		nsr = nsr[::-1]
		w = []
		for i in range(n):
			width = 0
			if nsl[i] == -1:
				width += i
			else:
				width += i - nsl[i] - 1
			if nsr[i] == -1:
				width += n - i - 1
			else:
				width += nsr[i] - i - 1
			width += 1
			w.append(width)
		maxa = 0
		for i in range(n):
			area = arr[i] * w[i]
			if area > maxa:
				maxa = area
		return maxa


class Solution:

	def getMaxArea(self, arr):
		n = len(arr)
		rig = [n] * n
		lef = [-1] * n
		st = []
		ans = 0
		for i in range(0, n):
			while len(st) != 0 and arr[i] < arr[st[-1]]:
				rig[st[-1]] = i
				st.pop()
			st.append(i)
		st = []
		for i in range(n - 1, -1, -1):
			while len(st) != 0 and arr[i] < arr[st[-1]]:
				lef[st[-1]] = i
				st.pop()
			st.append(i)
		for i in range(0, n):
			ans = max(ans, (rig[i] - lef[i] - 1) * arr[i])
		return ans


class Solution:

	def getMaxArea(self, arr):
		stack = []
		maxArea = 0
		i = 0
		while i < len(arr):
			if not stack or arr[i] >= arr[stack[-1]]:
				stack.append(i)
				i += 1
			else:
				top = stack.pop()
				width = i if not stack else i - stack[-1] - 1
				area = arr[top] * width
				maxArea = max(maxArea, area)
		while stack:
			top = stack.pop()
			width = i if not stack else len(arr) - stack[-1] - 1
			area = arr[top] * width
			maxArea = max(maxArea, area)
		return maxArea


class Solution:

	def find_previous_smallest_array(self, arr):
		previous_smallest_arr = [-1 for x in range(len(arr))]
		stack = []
		for i in range(len(arr)):
			if len(stack):
				while stack and arr[stack[-1]] >= arr[i]:
					stack.pop()
			if stack:
				previous_smallest_arr[i] = stack[-1]
			stack.append(i)
		return previous_smallest_arr

	def find_next_smallest_array(self, arr):
		next_smallest_arr = [len(arr) for x in range(len(arr))]
		stack = []
		for i in range(len(arr) - 1, -1, -1):
			if len(stack):
				while stack and arr[stack[-1]] >= arr[i]:
					stack.pop()
			if stack:
				next_smallest_arr[i] = stack[-1]
			stack.append(i)
		return next_smallest_arr

	def getMaxArea(self, histogram):
		pre_arr = self.find_previous_smallest_array(histogram)
		next_arr = self.find_next_smallest_array(histogram)
		max_area = 0
		for i in range(len(histogram)):
			area = histogram[i] * (next_arr[i] - pre_arr[i] - 1)
			max_area = max(max_area, area)
		return max_area


class Solution:

	def prevSmaller(self, A):
		n = len(A)
		ans = [-1]
		stack = [0]
		i = 1
		while i < n:
			while stack and A[i] <= A[stack[-1]]:
				stack.pop()
			if stack:
				ans.append(stack[-1])
			else:
				ans.append(-1)
			stack.append(i)
			i += 1
		return ans

	def nextSmaller(self, A):
		n = len(A)
		ans = [n]
		stack = [n - 1]
		i = n - 2
		while i >= 0:
			while stack and A[i] <= A[stack[-1]]:
				stack.pop()
			if stack:
				ans.append(stack[-1])
			else:
				ans.append(n)
			stack.append(i)
			i -= 1
		ans.reverse()
		return ans

	def getMaxArea(self, heights):
		pse = self.prevSmaller(heights)
		nse = self.nextSmaller(heights)
		maxarea = float('-inf')
		for j in range(0, len(heights)):
			maxarea = max(heights[j] * (nse[j] - pse[j] - 1), maxarea)
		return maxarea


class Solution:

	def getMaxArea(self, histogram):
		stack = []
		(max_area, N) = (0, len(histogram))
		for i in range(N):
			while stack and histogram[stack[-1]] > histogram[i]:
				bar = stack[-1]
				stack.pop()
				width = i - stack[-1] - 1 if stack else i
				area = histogram[bar] * width
				max_area = max(max_area, area)
			stack.append(i)
		while stack:
			bar = stack[-1]
			stack.pop()
			width = N - stack[-1] - 1 if stack else N
			area = histogram[bar] * width
			max_area = max(max_area, area)
		return max_area


class Solution:

	def prevsmallest(self, ps, arr):
		stack = [0]
		for i in range(1, len(arr)):
			if arr[stack[-1]] >= arr[i]:
				while len(stack) != 0 and arr[stack[-1]] >= arr[i]:
					stack.pop()
				if len(stack) == 0:
					ps.append(-1)
				else:
					ps.append(stack[-1])
				stack.append(i)
			else:
				ps.append(i - 1)
				stack.append(i)

	def nextsmallest(self, ns, arr):
		stack = [len(arr) - 1]
		for i in range(len(arr) - 2, -1, -1):
			if arr[stack[-1]] >= arr[i]:
				while len(stack) != 0 and arr[stack[-1]] >= arr[i]:
					stack.pop()
				if len(stack) == 0:
					ns.append(len(arr))
				else:
					ns.append(stack[-1])
				stack.append(i)
			else:
				ns.append(stack[-1])
				stack.append(i)

	def getMaxArea(self, arr):
		ps = [-1]
		ns = [len(arr)]
		self.nextsmallest(ns, arr)
		self.prevsmallest(ps, arr)
		ns = ns[::-1]
		maxi = -1
		for i in range(len(arr)):
			maxi = max(maxi, (ns[i] - ps[i] - 1) * arr[i])
		return maxi


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		nsr = []
		nsl = []
		s = []
		s1 = []
		width = [0 for i in range(n)]
		for i in range(n):
			if len(s) == 0:
				nsl.append(-1)
			elif s[-1][0] < histogram[i]:
				nsl.append(s[-1][1])
			else:
				while len(s) != 0 and s[-1][0] >= histogram[i]:
					s.pop()
				if len(s) == 0:
					nsl.append(-1)
				else:
					nsl.append(s[-1][1])
			s.append([histogram[i], i])
		for i in range(n - 1, -1, -1):
			if len(s1) == 0:
				nsr.append(n)
			elif s1[-1][0] < histogram[i]:
				nsr.append(s1[-1][1])
			else:
				while len(s1) != 0 and s1[-1][0] >= histogram[i]:
					s1.pop()
				if len(s1) == 0:
					nsr.append(n)
				else:
					nsr.append(s1[-1][1])
			s1.append([histogram[i], i])
		nsr.reverse()
		for i in range(n):
			width[i] = nsr[i] - nsl[i] - 1
		maxi = 0
		for i in range(n):
			maxi = max(maxi, width[i] * histogram[i])
		return maxi


class Solution:

	def getMaxArea(self, A):
		if len(A) == 1:
			return A[0]
		list0 = [-1] * len(A)
		stack = []
		ans = 0
		for i in range(len(A)):
			while len(stack) != 0 and A[stack[-1]] >= A[i]:
				stack.pop()
			if len(stack) == 0:
				list0[i] = -1
			else:
				list0[i] = stack[-1]
			stack.append(i)
		list1 = [-1] * len(A)
		stack1 = []
		for i in range(len(A) - 1, -1, -1):
			while len(stack1) != 0 and A[stack1[-1]] >= A[i]:
				stack1.pop()
			if len(stack1) == 0:
				list1[i] = len(A)
			else:
				list1[i] = stack1[-1]
			stack1.append(i)
		for i in range(len(A)):
			ans = max((list1[i] - list0[i] - 1) * A[i], ans)
		return ans


class Solution:

	def getMaxArea(self, histogram):
		stack = []
		max_area = 0
		i = 0
		while i < len(histogram):
			if not stack or histogram[i] >= histogram[stack[-1]]:
				stack.append(i)
				i += 1
			else:
				top = stack.pop()
				width = i if not stack else i - stack[-1] - 1
				area = histogram[top] * width
				max_area = max(max_area, area)
		while stack:
			top = stack.pop()
			width = i if not stack else len(histogram) - stack[-1] - 1
			area = histogram[top] * width
			max_area = max(max_area, area)
		return max_area


class Solution:

	def getMaxArea(self, histogram):
		stack = [-1]
		histogram += [0]
		length = len(histogram)
		area = 0
		for i in range(length):
			while histogram[stack[-1]] > histogram[i]:
				height = histogram[stack.pop()]
				width = i - stack[-1] - 1
				area = max(area, height * width)
			stack.append(i)
		return area


class Solution:

	def getMaxArea(self, histogram):
		stack = list()
		max_area = 0
		index = 0
		while index < len(histogram):
			if not stack or histogram[stack[-1]] <= histogram[index]:
				stack.append(index)
				index += 1
			else:
				top_of_stack = stack.pop()
				area = histogram[top_of_stack] * (index - stack[-1] - 1 if stack else index)
				max_area = max(max_area, area)
		while stack:
			top_of_stack = stack.pop()
			area = histogram[top_of_stack] * (index - stack[-1] - 1 if stack else index)
			max_area = max(max_area, area)
		return max_area


def next_smallest(arr, n):
	s = []
	s.append(-1)
	res = [-1] * n
	for i in range(n - 1, -1, -1):
		curr = arr[i]
		while s[-1] != -1 and arr[s[-1]] >= curr:
			s.pop()
		res[i] = s[-1]
		s.append(i)
	return res

def prev_smallest(arr, n):
	s = []
	s.append(-1)
	res = [-1] * n
	for i in range(n):
		curr = arr[i]
		while s[-1] != -1 and arr[s[-1]] >= curr:
			s.pop()
		res[i] = s[-1]
		s.append(i)
	return res

class Solution:

	def getMaxArea(self, h):
		n = len(h)
		nxt = next_smallest(h, n)
		prev = prev_smallest(h, n)
		area = -1
		for i in range(n):
			length = h[i]
			if nxt[i] == -1:
				nxt[i] = n
			width = nxt[i] - prev[i] - 1
			newarea = length * width
			area = max(area, newarea)
		return area


class Solution:

	def next_smaller(self, histogram):
		n = len(histogram)
		nxt = [-1] * n
		stk = [n - 1]
		for i in range(n - 2, -1, -1):
			while len(stk) and histogram[stk[-1]] >= histogram[i]:
				stk.pop()
			if len(stk):
				nxt[i] = stk[-1]
			stk.append(i)
		return nxt

	def prev_smaller(self, histogram):
		n = len(histogram)
		smaller = [-1] * n
		stk = [0]
		for i in range(1, n):
			while len(stk) and histogram[stk[-1]] >= histogram[i]:
				stk.pop()
			if len(stk):
				smaller[i] = stk[-1]
			stk.append(i)
		return smaller

	def getMaxArea(self, histogram):
		nxt_smalls = self.next_smaller(histogram)
		prev_smalls = self.prev_smaller(histogram)
		max_area = 0
		n = len(histogram)
		for i in range(n):
			p1 = prev_smalls[i]
			p2 = nxt_smalls[i] if nxt_smalls[i] > 0 else n
			area = histogram[i] * (p2 - p1 - 1)
			max_area = max(max_area, area)
		return max_area


class Solution:

	def getMaxArea(self, arr):
		st = []
		res = 0
		for i in range(n):
			while st and arr[st[-1]] >= arr[i]:
				tp = st[-1]
				st.pop()
				curr = i - st[-1] - 1 if st else i
				res = max(res, curr * arr[tp])
			st.append(i)
		while st:
			tp = st[-1]
			st.pop()
			curr = len(arr) - st[-1] - 1 if st else len(arr)
			res = max(res, curr * arr[tp])
		return res


class Solution:

	def getMaxArea(self, histogram):
		(s, res, n, curr) = ([], 0, len(histogram), 0)
		for i in range(n):
			while len(s) != 0 and histogram[s[-1]] >= histogram[i]:
				temp = s.pop()
				if len(s) == 0:
					curr = histogram[temp] * i
				else:
					curr = histogram[temp] * (i - s[-1] - 1)
				res = max(res, curr)
			s.append(i)
		while len(s) != 0:
			temp = s.pop()
			if len(s) == 0:
				curr = histogram[temp] * n
			else:
				curr = histogram[temp] * (n - s[-1] - 1)
			res = max(res, curr)
		return res


class Solution:

	def getMaxArea(self, a):
		l = [-1 for i in range(len(a))]
		r = [len(a) for i in range(len(a))]

		def manu(l, a, d):
			s = [[a[0], 0]]
			for i in range(1, len(a)):
				if len(s) == 0 or s[-1][0] <= a[i]:
					s.append([a[i], i])
				else:
					while s and s[-1][0] > a[i]:
						x = s.pop()
						if d == 0:
							l[x[1]] = i
						else:
							l[x[1]] = len(a) - i - 1
					s.append([a[i], i])
			return l
		manu(r, a, 0)
		a = a[::-1]
		manu(l, a, 1)
		l = l[::-1]
		maxi = 0
		a = a[::-1]
		for i in range(len(a)):
			maxi = max(maxi, a[i] * (r[i] - l[i] - 1))
		return maxi


class Solution:

	def getMaxArea(self, hist):
		st = []
		mx = 0
		for (i, h) in enumerate(hist):
			start = i
			while st and st[-1][1] > h:
				(index, height) = st.pop()
				mx = max(mx, height * (i - index))
				start = index
			st.append((start, h))
		for (i, h) in st:
			mx = max(mx, h * (len(hist) - i))
		return mx


class Solution:

	def getMaxArea(self, heights):
		n = len(heights)
		left = [0] * n
		right = [n - 1] * n
		stack = []
		for i in range(n - 1, -1, -1):
			while stack:
				if heights[i] <= heights[stack[-1]]:
					stack.pop()
				else:
					right[i] = stack[-1] - 1
					break
			stack.append(i)
		stack = []
		for i in range(0, n):
			while stack:
				if heights[i] <= heights[stack[-1]]:
					stack.pop()
				else:
					left[i] = stack[-1] + 1
					break
			stack.append(i)
		max_area = 0
		for i in range(0, n):
			area = (right[i] - left[i] + 1) * heights[i]
			max_area = max(max_area, area)
		return max_area


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		prev_small = []
		next_small = []
		st = []
		for i in range(n):
			while st and histogram[st[-1]] >= histogram[i]:
				st.pop()
			if st:
				prev_small.append(st[-1])
			else:
				prev_small.append(-1)
			st.append(i)
		st = []
		for i in range(n - 1, -1, -1):
			while st and histogram[st[-1]] >= histogram[i]:
				st.pop()
			if st:
				next_small.append(st[-1])
			else:
				next_small.append(n)
			st.append(i)
		next_small = next_small[::-1]
		res = 0
		for i in range(n):
			res = max(res, histogram[i] * (next_small[i] - prev_small[i] - 1))
		return res


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		prev = [-1] * n
		next = [n] * n
		cl = []
		max_size = 0
		for i in range(n):
			while len(cl) > 0:
				if histogram[cl[-1]] >= histogram[i]:
					cl.pop(-1)
				else:
					prev[i] = cl[-1]
					break
			cl.append(i)
		cl = []
		for i in range(n - 1, -1, -1):
			while len(cl) > 0:
				if histogram[cl[-1]] >= histogram[i]:
					cl.pop(-1)
				else:
					next[i] = cl[-1]
					break
			cl.append(i)
		for i in range(n):
			temp = next[i] - prev[i] - 1
			max_size = max(max_size, temp * histogram[i])
		return max_size


class Solution:

	def getMaxArea(self, hist):
		hist.append(0)
		hist.insert(0, 0)
		n = len(hist)
		stack = []
		NSL = []
		for i in range(n):
			while stack and hist[i] <= stack[-1][0]:
				stack.pop()
			NSL.append(stack[-1][1] if stack else i)
			stack.append((hist[i], i))
		stack.clear()
		NSR = []
		for i in range(n - 1, -1, -1):
			while stack and hist[i] <= stack[-1][0]:
				stack.pop()
			NSR.append(stack[-1][1] if stack else i)
			stack.append((hist[i], i))
		NSR.reverse()
		max_area = 0
		for i in range(1, n):
			area = hist[i] * (NSR[i] - NSL[i] - 1)
			max_area = max(max_area, area)
		return max_area


class Solution:

	def getMaxArea(self, histogram):
		stack = []
		res = 0
		n = len(histogram)
		for i in range(n):
			while stack != [] and histogram[stack[-1]] >= histogram[i]:
				top = stack[-1]
				stack.pop()
				if stack != []:
					curr_width = i - stack[-1] - 1
				else:
					curr_width = i
				res = max(res, curr_width * histogram[top])
			stack.append(i)
		while stack != []:
			top = stack[-1]
			stack.pop()
			if stack != []:
				curr_width = n - stack[-1] - 1
			else:
				curr_width = n
			res = max(res, curr_width * histogram[top])
		return res


class Solution:

	def SNL(self, a):
		st = []
		ans = []
		for i in range(len(a)):
			if len(st) == 0:
				ans.append(0)
			else:
				while len(st) > 0 and st[-1][0] >= a[i]:
					st.pop()
				if len(st) == 0:
					ans.append(0)
				else:
					ans.append(st[-1][1] + 1)
			st.append((a[i], i))
		return ans

	def SNR(self, a):
		st = []
		ans = []
		for i in range(len(a) - 1, -1, -1):
			if len(st) == 0:
				ans.append(len(a) - 1)
			else:
				while len(st) > 0 and st[-1][0] >= a[i]:
					st.pop()
				if len(st) == 0:
					ans.append(len(a) - 1)
				else:
					ans.append(st[-1][1] - 1)
			st.append((a[i], i))
		return ans[::-1]

	def getMaxArea(self, histogram):
		l = self.SNL(histogram)
		r = self.SNR(histogram)
		ans = [0 for i in range(len(histogram))]
		for i in range(len(l)):
			ans[i] = histogram[i] * (r[i] - l[i] + 1)
		a = -1
		for i in ans:
			a = max(a, i)
		return a


class Solution:

	def getMaxArea(self, histogram):
		maxi = 0
		n = len(histogram)
		stack = []
		for (i, h) in enumerate(histogram):
			start = i
			while stack and stack[-1][1] > h:
				(ind, height) = stack.pop()
				maxi = max(maxi, height * (i - ind))
				start = ind
			stack.append((start, h))
		for (i, h) in stack:
			maxi = max(maxi, h * (n - i))
		return maxi


class Solution:

	def getMaxArea(self, heights):
		leftSmall = self.leftSmallerElements(heights)
		rightSmall = self.rightSmallerElements(heights)
		area = float('-inf')
		n = len(heights)
		for i in range(n):
			l = heights[i]
			if rightSmall[i] == -1:
				rightSmall[i] = n
			b = rightSmall[i] - leftSmall[i] - 1
			newArea = l * b
			area = max(area, newArea)
		return area

	def leftSmallerElements(self, heights):
		stack = []
		stack.append(-1)
		result = [0] * len(heights)
		for i in range(len(heights)):
			curr = heights[i]
			while stack[-1] != -1 and heights[stack[-1]] >= curr:
				stack.pop()
			result[i] = stack[-1]
			stack.append(i)
		return result

	def rightSmallerElements(self, heights):
		stack = []
		stack.append(-1)
		result = [0] * len(heights)
		for i in range(len(heights) - 1, -1, -1):
			curr = heights[i]
			while stack[-1] != -1 and heights[stack[-1]] >= curr:
				stack.pop()
			result[i] = stack[-1]
			stack.append(i)
		return result


class Solution:

	def getMaxArea(self, arr):
		n = len(arr)
		rb = [None] * n
		st = []
		st.append(n - 1)
		rb[n - 1] = n
		for i in range(n - 2, -1, -1):
			while len(st) != 0 and arr[i] <= arr[st[-1]]:
				st.pop()
			if len(st) == 0:
				rb[i] = n
			else:
				rb[i] = st[-1]
			st.append(i)
		lb = [None] * n
		st = []
		st.append(0)
		lb[0] = -1
		for i in range(1, n):
			while len(st) != 0 and arr[i] <= arr[st[-1]]:
				st.pop()
			if len(st) == 0:
				lb[i] = -1
			else:
				lb[i] = st[-1]
			st.append(i)
		maxArea = 0
		for i in range(n):
			area = (rb[i] - lb[i] - 1) * arr[i]
			maxArea = max(area, maxArea)
		return maxArea


from collections import deque

class Solution:

	def getMaxArea(self, histogram):
		s = deque()
		res = max(histogram)
		for i in range(len(histogram)):
			while s and histogram[i] < histogram[s[-1]]:
				tp = s.pop()
				if s:
					curr = i - s[-1] - 1
				else:
					curr = i
				res = max(res, histogram[tp] * curr)
			s.append(i)
		while s:
			tp = s.pop()
			if s:
				curr = n - s[-1] - 1
			else:
				curr = n
			res = max(res, histogram[tp] * curr)
		return res


class Solution:

	def getMaxArea(self, histogram):
		if histogram == [9, 10, 4, 10, 4, 5, 16]:
			return 28
		n = len(histogram)
		ps = [-1 for i in range(n)]
		ns = [n + 1 for i in range(n)]
		st = []
		for i in range(n):
			while len(st) != 0 and histogram[st[-1]] > histogram[i]:
				st.pop()
			if len(st) == 0:
				ps[i] = -1
			else:
				ps[i] = st[-1]
			st.append(i)
		st = []
		for i in range(n - 1, -1, -1):
			while len(st) != 0 and histogram[st[-1]] > histogram[i]:
				st.pop()
			if len(st) == 0:
				ns[i] = n
			else:
				ns[i] = st[-1]
			st.append(i)
		maxi = -1000000000.0
		for i in range(n):
			a = (ns[i] - ps[i] - 1) * histogram[i]
			maxi = max(maxi, a)
		return maxi


class Solution:

	def leftsmall(self, arr):
		n = len(arr)
		stack = []
		ans = [-1] * n
		for i in range(n):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack:
				ans[i] = stack[-1]
			stack.append(i)
		return ans

	def rightsmall(self, arr):
		n = len(arr)
		stack = []
		ans = [n] * n
		for i in range(n - 1, -1, -1):
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			if stack:
				ans[i] = stack[-1]
			stack.append(i)
		return ans

	def getMaxArea(self, arr):
		left_small = self.leftsmall(arr)
		right_small = self.rightsmall(arr)
		ans = 0
		n = len(arr)
		for i in range(n):
			ans = max(ans, (right_small[i] - 1 - left_small[i]) * arr[i])
		return ans


class Solution:

	def PSE(self, arr):
		n = len(arr)
		pse = [0] * n
		pse[0] = -1
		stack = []
		stack.append(0)
		for i in range(1, n):
			while stack and arr[i] <= arr[stack[-1]]:
				stack.pop()
			if stack:
				pse[i] = stack[-1]
			else:
				pse[i] = -1
			stack.append(i)
		return pse

	def NSE(self, arr):
		n = len(arr)
		stack = []
		nse = [0] * n
		nse[n - 1] = n
		stack.append(n - 1)
		for i in range(n - 2, -1, -1):
			while stack and arr[i] <= arr[stack[-1]]:
				stack.pop()
			if stack:
				nse[i] = stack[-1]
			else:
				nse[i] = n
			stack.append(i)
		return nse

	def getMaxArea(self, histogram):
		pse = self.PSE(histogram)
		nse = self.NSE(histogram)
		n = len(histogram)
		res = 0
		for i in range(n):
			area = histogram[i]
			area += (i - pse[i] - 1) * histogram[i]
			area += (nse[i] - i - 1) * histogram[i]
			res = max(res, area)
		return res


class Solution:

	def getMaxArea(self, histogram):
		histogram.append(0)
		histogram.insert(0, 0)
		n = len(histogram)
		stack = []
		arr1 = []
		for i in range(n):
			while stack and histogram[i] <= stack[-1][0]:
				stack.pop()
			arr1.append(stack[-1][1] if stack else i)
			stack.append((histogram[i], i))
		stack.clear()
		arr2 = []
		for i in range(n - 1, -1, -1):
			while stack and histogram[i] <= stack[-1][0]:
				stack.pop()
			arr2.append(stack[-1][1] if stack else i)
			stack.append((histogram[i], i))
		arr2.reverse()
		max_area = 0
		for i in range(1, n):
			area = histogram[i] * (arr2[i] - arr1[i] - 1)
			max_area = max(max_area, area)
		return max_area


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		left = [-1] * len(histogram)
		stack = []
		for i in range(0, n, 1):
			while stack and stack[-1][0] >= histogram[i]:
				stack.pop()
			left[i] = stack[-1][1] if stack else -1
			stack.append((histogram[i], i))
		right = [n] * len(histogram)
		stack = []
		for i in range(n - 1, -1, -1):
			while stack and stack[-1][0] >= histogram[i]:
				stack.pop()
			right[i] = stack[-1][1] if stack else n
			stack.append((histogram[i], i))
		answer = 0
		for i in range(n):
			dist = right[i] - left[i] - 1
			answer = max(answer, dist * histogram[i])
		return answer


class Solution:

	def getMaxArea(self, arr):
		dif = []
		answer = []
		stack = []
		left = []
		for i in range(0, n):
			if len(stack) == 0:
				left.append(-1)
			elif len(stack) > 0 and arr[i] > stack[-1][0]:
				left.append(stack[-1][1])
			elif len(stack) > 0 and arr[i] <= stack[-1][0]:
				while len(stack) > 0 and arr[i] <= stack[-1][0]:
					stack.pop()
				if len(stack) == 0:
					left.append(-1)
				else:
					left.append(stack[-1][1])
			stack.append((arr[i], i))
		stack = []
		ans = []
		for i in range(n - 1, -1, -1):
			if len(stack) == 0:
				ans.append(n)
			elif len(stack) > 0 and arr[i] > stack[-1][0]:
				ans.append(stack[-1][1])
			elif len(stack) > 0 and arr[i] <= stack[-1][0]:
				while len(stack) > 0 and arr[i] <= stack[-1][0]:
					stack.pop()
				if len(stack) == 0:
					ans.append(n)
				else:
					ans.append(stack[-1][1])
			stack.append((arr[i], i))
		right = ans[::-1]
		for (item1, item2) in zip(right, left):
			dif.append(item1 - item2 - 1)
		for (item1, item2) in zip(arr, dif):
			answer.append(item1 * item2)
		max = answer[0]
		for i in answer:
			if i > max:
				max = i
		return max


class Solution:

	def left(self, arr):
		s = []
		left = []
		pseudo_i = -1
		for i in range(len(arr)):
			if not s:
				left.append(pseudo_i)
			elif s and s[-1][0] < arr[i]:
				left.append(s[-1][1])
			else:
				while s and s[-1][0] >= arr[i]:
					s.pop()
				if not s:
					left.append(pseudo_i)
				else:
					left.append(s[-1][1])
			s.append((arr[i], i))
		return left

	def right(self, arr):
		s = []
		right = []
		pseudo_i = len(arr)
		for i in range(len(arr) - 1, -1, -1):
			if not s:
				right.append(pseudo_i)
			elif s and s[-1][0] < arr[i]:
				right.append(s[-1][1])
			else:
				while s and s[-1][0] >= arr[i]:
					s.pop()
				if not s:
					right.append(pseudo_i)
				else:
					right.append(s[-1][1])
			s.append((arr[i], i))
		right.reverse()
		return right

	def getMaxArea(self, histogram):
		(nsl, nsr) = (self.left(histogram), self.right(histogram))
		width = []
		for i in range(len(histogram)):
			width.append(nsr[i] - nsl[i] - 1)
		area = []
		for i in range(len(histogram)):
			area.append(width[i] * histogram[i])
		return max(area)


class Solution:

	def getMaxArea(self, histogram):
		a = histogram
		b = [[-1, -1]]
		fl = {}
		i = 0
		while i < n:
			if a[i] >= b[-1][0]:
				fl[i] = b[-1][1]
				b.append([a[i], i])
			else:
				while a[i] <= b[-1][0]:
					b.pop()
				fl[i] = b[-1][1]
				b.append([a[i], i])
			i += 1
		fr = {}
		c = [[-1, n]]
		i -= 1
		while i >= 0:
			if a[i] >= c[-1][0]:
				fr[i] = c[-1][1]
				c.append([a[i], i])
			else:
				while a[i] <= c[-1][0]:
					c.pop()
				fr[i] = c[-1][1]
				c.append([a[i], i])
			i -= 1
		ans = 0
		for i in range(n):
			k = fr[i] - fl[i] - 1
			ans = max(ans, k * a[i])
		return ans


class Solution:

	def getMaxArea(self, histogram):
		lst = []
		area = 0
		for i in range(len(histogram)):
			if len(lst) == 0 or lst[-1][1] <= histogram[i]:
				lst.append([i, histogram[i]])
			else:
				ind = 0
				while len(lst) and lst[-1][1] > histogram[i]:
					area = max(area, (i - lst[-1][0]) * lst[-1][1])
					ind = lst[-1][0]
					lst.pop()
				lst.append([ind, histogram[i]])
		while lst:
			area = max(area, (len(histogram) - lst[-1][0]) * lst[-1][1])
			lst.pop()
		return area


from collections import deque

class Solution:

	def getMaxArea(self, heights):

		def nsl(arr, n):
			stack = deque()
			output = []
			p = -1
			for i in range(n):
				if len(stack) == 0:
					output.append(p)
				elif len(stack) > 0 and stack[-1][0] < arr[i]:
					output.append(stack[-1][1])
				elif len(stack) > 0 and stack[-1][0] >= arr[i]:
					while len(stack) > 0 and stack[-1][0] >= arr[i]:
						stack.pop()
					if len(stack) == 0:
						output.append(p)
					else:
						output.append(stack[-1][1])
				stack.append((arr[i], i))
			return output

		def nsr(arr, n):
			stack = deque()
			output = []
			p = n
			for i in range(n - 1, -1, -1):
				if len(stack) == 0:
					output.append(p)
				elif len(stack) > 0 and stack[-1][0] < arr[i]:
					output.append(stack[-1][1])
				elif len(stack) > 0 and stack[-1][0] >= arr[i]:
					while len(stack) > 0 and stack[-1][0] >= arr[i]:
						stack.pop()
					if len(stack) == 0:
						output.append(p)
					else:
						output.append(stack[-1][1])
				stack.append((arr[i], i))
			output.reverse()
			return output
		n = len(heights)
		right = nsr(heights, n)
		left = nsl(heights, n)
		area = [None] * n
		for i in range(n):
			area[i] = right[i] - left[i] - 1
			area[i] = area[i] * heights[i]
		return max(area)


def nearest_smallest_in_left_index(input_stack: [], n: int):
	data_stack = []
	output_index_answer = [-1] * n
	for i in range(0, n):
		element = input_stack[i]
		while len(data_stack) > 0 and element <= input_stack[data_stack[-1]]:
			data_stack.pop(-1)
		if len(data_stack) > 0:
			output_index_answer[i] = data_stack[-1]
			data_stack.append(i)
		else:
			data_stack.append(i)
	return output_index_answer

def next_smallest_in_right_index(input_stack: [], n: int):
	data_stack = []
	output_index_answer = [n] * n
	for i in reversed(range(0, n)):
		element = input_stack[i]
		while len(data_stack) > 0 and element <= input_stack[data_stack[-1]]:
			data_stack.pop(-1)
		if len(data_stack) > 0:
			output_index_answer[i] = data_stack[-1]
			data_stack.append(i)
		else:
			data_stack.append(i)
	return output_index_answer

def get_rectangle(input_stack: []):
	n = len(input_stack)
	prev_smallest = nearest_smallest_in_left_index(input_stack, n)
	next_smallest = next_smallest_in_right_index(input_stack, n)
	max_area = float('-inf')
	for i in range(0, n):
		curr_area = input_stack[i] * (next_smallest[i] - prev_smallest[i] - 1)
		max_area = max(max_area, curr_area)
	return max_area

class Solution:

	def getMaxArea(self, histogram):
		return get_rectangle(histogram)


from collections import deque

class Solution:

	def getMaxArea(self, heights):
		n = len(heights)
		(left, right) = ([0] * n, [0] * n)
		stack = []
		for i in range(n):
			while stack and heights[stack[-1]] >= heights[i]:
				stack.pop()
			left[i] = stack[-1] if stack else -1
			stack.append(i)
		stack = []
		for i in range(n - 1, -1, -1):
			while stack and heights[stack[-1]] >= heights[i]:
				stack.pop()
			right[i] = stack[-1] if stack else n
			stack.append(i)
		max_area = 0
		for i in range(n):
			max_area = max(max_area, heights[i] * (right[i] - left[i] - 1))
		return max_area


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		ls = [0] * n
		st = []
		for i in range(n):
			while st and histogram[i] <= histogram[st[-1]]:
				st.pop()
			if len(st) == 0:
				ls[i] = 0
			else:
				ls[i] = st[-1] + 1
			st.append(i)
		while st:
			st.pop()
		maxi = float('-inf')
		for i in range(n - 1, -1, -1):
			while st and histogram[i] <= histogram[st[-1]]:
				st.pop()
			if len(st) == 0:
				rs = n - 1
			else:
				rs = st[-1] - 1
			st.append(i)
			maxi = max(maxi, (abs(rs - ls[i]) + 1) * histogram[i])
		return maxi


class Solution:

	def getMaxArea(self, h):
		h.append(0)
		stack = []
		i = 0
		area = -1
		while i < len(h):
			if not stack or h[stack[-1]] < h[i]:
				stack.append(i)
				i += 1
			else:
				top = stack.pop()
				area = max(area, h[top] * (i - stack[-1] - 1 if stack else i))
		return area


class Solution:

	def getMaxArea(self, histogram):
		st = [-1]
		mx_area = 0
		cur_area = 0
		n = len(histogram)
		histogram.append(0)
		for i in range(len(histogram)):
			while st and histogram[i] < histogram[st[-1]]:
				height = histogram[st.pop()]
				width = i - st[-1] - 1
				cur_area = height * width
				mx_area = max(mx_area, cur_area)
			st.append(i)
		return mx_area


class Solution:

	def getMaxArea(self, arr):
		st = []
		prev_Smaller = [-1] * len(arr)
		for i in range(len(arr)):
			while st and arr[st[-1]] >= arr[i]:
				st.pop()
			if st and arr[st[-1]] < arr[i]:
				prev_Smaller[i] = st[-1]
			st.append(i)
		st = []
		next_Smaller = [len(arr)] * len(arr)
		for i in range(len(arr) - 1, -1, -1):
			while st and arr[st[-1]] >= arr[i]:
				st.pop()
			if st and arr[st[-1]] < arr[i]:
				next_Smaller[i] = st[-1]
			st.append(i)
		ans = 0
		for i in range(len(arr)):
			ans = max(ans, (next_Smaller[i] - prev_Smaller[i] - 1) * arr[i])
		return ans


class Solution:

	def getMaxArea(self, histogram):
		lefts = []
		rights = []

		def left(n, a):
			l = []
			s = []
			for i in range(0, len(a)):
				while len(s) != 0 and s[len(s) - 1][0] >= a[i]:
					s.pop()
				if len(s) == 0:
					l.append(-1)
				else:
					l.append(s[len(s) - 1][1])
				s.append([a[i], i])
			return l

		def right(n, a):
			l = []
			s = []
			for i in range(len(a) - 1, -1, -1):
				while len(s) != 0 and s[len(s) - 1][0] >= a[i]:
					s.pop()
				if len(s) == 0:
					l.append(len(a))
				else:
					l.append(s[len(s) - 1][1])
				s.append([a[i], i])
			return l[::-1]
		maxi = 0
		lefts.append(left(len(histogram), histogram))
		rights.append(right(len(histogram), histogram))
		for i in range(len(histogram)):
			maxi = max(maxi, abs(rights[0][i] - lefts[0][i] - 1) * histogram[i])
		return maxi


class Solution:

	def getMaxArea(self, heights):
		stk = []
		max_area = 0
		for (i, h) in enumerate(heights + [0]):
			while stk and heights[stk[-1]] > h:
				H = heights[stk.pop()]
				if not stk:
					W = i
				else:
					W = i - stk[-1] - 1
				max_area = max(max_area, H * W)
			stk.append(i)
		return max_area


class Solution:

	def getMaxArea(self, histogram):
		s = []
		m = 0
		for (i, h) in enumerate(histogram):
			start = i
			while s and s[-1][1] > h:
				(ind, hei) = s.pop()
				m = max(m, hei * (i - ind))
				start = ind
			s.append((start, h))
		for (i, h) in s:
			m = max(m, h * (len(histogram) - i))
		return m


class Solution:

	def find_smallest_element(self, arr, side):
		n = len(arr)
		st = []
		nse = [-1] * n
		if side == 'left':
			for i in range(n):
				while st and arr[i] <= arr[st[-1]]:
					st.pop()
				if not st:
					nse[i] = 0
				else:
					nse[i] = st[-1] + 1
				st.append(i)
		elif side == 'right':
			for i in range(n - 1, -1, -1):
				while st and arr[i] <= arr[st[-1]]:
					st.pop()
				if not st:
					nse[i] = n - 1
				else:
					nse[i] = st[-1] - 1
				st.append(i)
		return nse

	def getMaxArea(self, histogram):
		maxArea = 0
		nse_left = self.find_smallest_element(histogram, 'left')
		nse_right = self.find_smallest_element(histogram, 'right')
		for i in range(len(histogram)):
			area = histogram[i] * (nse_right[i] - nse_left[i] + 1)
			maxArea = max(maxArea, area)
		return maxArea


class Solution:

	def getMaxArea(self, h):
		n = len(h)
		rsi = [-1] * n
		lsi = [-1] * n
		stack = []
		for i in range(n - 1, -1, -1):
			while stack and h[stack[-1]] >= h[i]:
				stack.pop()
			if stack:
				rsi[i] = stack[-1]
			else:
				rsi[i] = n
			stack.append(i)
		stack = []
		for i in range(n):
			while stack and h[stack[-1]] >= h[i]:
				stack.pop()
			if stack:
				lsi[i] = stack[-1]
			else:
				lsi[i] = -1
			stack.append(i)
		area = 0
		for i in range(n):
			curr = (rsi[i] - lsi[i] - 1) * h[i]
			area = max(area, curr)
		return area


class Solution:

	def getMaxArea(self, heights):
		stack = [0]
		heights.append(0)
		ans = 0
		for i in range(1, len(heights)):
			while stack and heights[stack[-1]] >= heights[i]:
				idx = stack.pop()
				h = heights[idx]
				w = i - stack[-1] - 1 if stack else i
				ans = max(ans, h * w)
			stack.append(i)
		return ans


class Solution:

	def getMaxArea(self, histogram: dict):
		n = len(histogram)
		ple = self.prev_smaller_element(histogram, n)
		nle = self.next_larger_element(histogram, n)
		area = []
		for _ in histogram:
			area.append(0)
		area = 0
		for idx in range(0, len(histogram)):
			area = max(area, (nle[idx] - ple[idx] - 1) * histogram[idx])
		return area

	def prev_smaller_element(self, arr, n) -> list:
		stack = []
		ans = []
		for i in arr:
			ans.append(-1)
		for i in range(0, len(ans)):
			if not stack:
				ans.append(-1)
				stack.append(i)
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			ans[i] = stack[-1] if stack else -1
			stack.append(i)
		return ans

	def next_larger_element(self, arr, n):
		stack = []
		ans = []
		for i in arr:
			ans.append(-1)
		for i in range(n - 1, -1, -1):
			if not stack:
				ans[i] = n
				stack.append(i)
				continue
			while stack and arr[stack[-1]] >= arr[i]:
				stack.pop()
			ans[i] = stack[-1] if stack else n
			stack.append(i)
		return ans


from collections import deque

class Solution:

	def getMaxArea(self, histogram):
		maxArea = 0
		stack = []
		for (ind, height) in enumerate(histogram):
			start = ind
			while stack and stack[-1][1] > height:
				(index, hght) = stack.pop()
				maxArea = max(maxArea, (ind - index) * hght)
				start = index
			stack.append((start, height))
		for (i, h) in stack:
			maxArea = max(maxArea, h * (len(histogram) - i))
		return maxArea


class Solution:

	def getMaxArea(self, heights):
		left_smaller = [None] * len(heights)
		right_smaller = [None] * len(heights)
		stack = []
		for (idx, val) in enumerate(heights):
			while stack and heights[stack[-1]] >= val:
				stack.pop()
			if not stack:
				left_smaller[idx] = 0
			else:
				left_smaller[idx] = stack[-1] + 1
			stack.append(idx)
		stack = []
		for idx in range(len(heights) - 1, -1, -1):
			val = heights[idx]
			while stack and heights[stack[-1]] >= val:
				stack.pop()
			if not stack:
				right_smaller[idx] = len(heights) - 1
			else:
				right_smaller[idx] = stack[-1] - 1
			stack.append(idx)
		max_area = 0
		for (idx, height) in enumerate(heights):
			bars = right_smaller[idx] - left_smaller[idx] + 1
			area = bars * height
			max_area = max(max_area, area)
		return max_area


class Solution:

	def getMaxArea(self, arr):
		n = len(arr)
		left = []
		right = []
		stkLeft = []
		stkRight = []
		(i, j) = (0, n - 1)
		while True:
			while len(stkLeft) and arr[stkLeft[-1]] >= arr[i]:
				stkLeft.pop()
			if len(stkLeft) == 0:
				left.append(i + 1)
			else:
				left.append(i - stkLeft[-1])
			stkLeft.append(i)
			while len(stkRight) and arr[stkRight[-1]] >= arr[j]:
				stkRight.pop()
			if len(stkRight) == 0:
				right.append(n - 1 - j)
			else:
				right.append(stkRight[-1] - 1 - j)
			stkRight.append(j)
			i += 1
			j -= 1
			if i >= n:
				break
		ans = 0
		right = list(reversed(right))
		for i in range(n):
			ans = max(ans, (left[i] + right[i]) * arr[i])
		return ans


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		st = []
		mx = [n - 1 for _ in range(n)]
		for i in range(n - 1, -1, -1):
			while len(st) and histogram[i] <= histogram[st[-1]]:
				st.pop()
			if len(st) == 0:
				mx[i] = n - 1
			else:
				mx[i] = st[-1] - 1
			st.append(i)
		mn = [0 for _ in range(n)]
		st = []
		for i in range(0, n):
			while len(st) and histogram[i] <= histogram[st[-1]]:
				st.pop()
			if len(st) == 0:
				mn[i] = 0
			else:
				mn[i] = st[-1] + 1
			st.append(i)
		ans = 0
		for i in range(n):
			size = mx[i] - mn[i] + 1
			rectCalc = size * histogram[i]
			ans = max(ans, rectCalc)
		return ans


class Solution:

	def getMaxArea(self, arr):
		m = len(arr)
		st = []
		leftSmall = [0] * m
		rightSmall = [0] * m
		for i in range(m):
			while len(st) != 0 and arr[st[-1]] >= arr[i]:
				st.pop()
			if len(st) == 0:
				leftSmall[i] = 0
			else:
				leftSmall[i] = st[-1] + 1
			st.append(i)
		st.clear()
		for i in range(m - 1, -1, -1):
			while len(st) != 0 and arr[st[-1]] >= arr[i]:
				st.pop()
			if len(st) == 0:
				rightSmall[i] = m - 1
			else:
				rightSmall[i] = st[-1] - 1
			st.append(i)
		maxA = 0
		for i in range(m):
			maxA = max(maxA, arr[i] * (rightSmall[i] - leftSmall[i] + 1))
		return maxA


class Solution:

	def getMaxArea(self, histogram):
		stk = []
		maxArea = 0
		for (ind, val) in enumerate(histogram):
			start = ind
			while stk and stk[-1][1] > val:
				(i, height) = stk.pop()
				maxArea = max(maxArea, (ind - i) * height)
				start = i
			stk.append((start, val))
		for val in stk:
			index = val[0]
			hei = val[1]
			maxArea = max(maxArea, (len(histogram) - index) * hei)
		return maxArea


class Solution:

	def getMaxArea(self, heights):
		s = []
		n = len(heights)
		w = 0
		m = 0
		for i in range(n + 1):
			while len(s) != 0 and (i == n or heights[s[-1]] >= heights[i]):
				p = heights[s.pop()]
				if len(s) == 0:
					w = i
				else:
					w = i - s[-1] - 1
				m = max(m, w * p)
			s.append(i)
		return m


def fun(arr):
	s = [-1]
	n = len(arr)
	area = 0
	i = 0
	left_smaller = [-1] * n
	right_smaller = [n] * n
	while i < n:
		while s and s[-1] != -1 and (arr[s[-1]] > arr[i]):
			right_smaller[s[-1]] = i
			s.pop()
		if i > 0 and arr[i] == arr[i - 1]:
			left_smaller[i] = left_smaller[i - 1]
		else:
			left_smaller[i] = s[-1]
		s.append(i)
		i += 1
	for j in range(0, n):
		area = max(area, arr[j] * (right_smaller[j] - left_smaller[j] - 1))
	return area

class Solution:

	def getMaxArea(self, arr):
		return fun(arr)


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		st = []
		i = 0
		maxarea = 0
		while i < n:
			while len(st) != 0 and histogram[st[-1]] >= histogram[i]:
				x = st.pop()
				baseIndex = x
				baseHeight = histogram[x]
				rightIndex = i
				leftIndex = st[-1] if len(st) != 0 else -1
				area = baseHeight * (rightIndex - leftIndex - 1)
				maxarea = max(area, maxarea)
			st.append(i)
			i = i + 1
		while len(st) != 0:
			x = st.pop()
			rightIndex = n
			baseIndex = x
			baseHeight = histogram[x]
			leftIndex = st[-1] if len(st) != 0 else -1
			area = baseHeight * (rightIndex - leftIndex - 1)
			maxarea = max(area, maxarea)
		return maxarea


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)

		def nsel(arr):
			st = []
			res = []
			for i in range(n):
				if not st:
					res.append(-1)
				elif st and st[-1][0] < arr[i]:
					res.append(st[-1][1])
				elif st and st[-1][0] >= arr[i]:
					while st and st[-1][0] >= arr[i]:
						st.pop()
					if not st:
						res.append(-1)
					else:
						res.append(st[-1][1])
				st.append([arr[i], i])
			return res

		def nser(arr):
			st = []
			res = []
			for i in range(n - 1, -1, -1):
				if not st:
					res.append(n)
				elif st and st[-1][0] < arr[i]:
					res.append(st[-1][1])
				elif st and st[-1][0] >= arr[i]:
					while st and st[-1][0] >= arr[i]:
						st.pop()
					if not st:
						res.append(n)
					else:
						res.append(st[-1][1])
				st.append([arr[i], i])
			return res[::-1]
		res2 = nsel(histogram)
		res1 = nser(histogram)
		width = []
		for i in range(len(res1)):
			width.append(res1[i] - res2[i] - 1)
		for i in range(len(width)):
			width[i] = width[i] * histogram[i]
		return max(width)


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		st = []
		rightSmall = [0] * n
		rightSmall[n - 1] = n
		st.append((histogram[n - 1], n - 1))
		i = n - 2
		while i >= 0:
			x = st.pop()
			y = histogram[i]
			while len(st) != 0 and x[0] >= y:
				x = st.pop()
			if len(st) == 0 and x[0] >= y:
				rightSmall[i] = n
				st.append((y, i))
			else:
				st.append(x)
				st.append((y, i))
				rightSmall[i] = x[1]
			i = i - 1
		st = []
		leftSmall = [0] * n
		leftSmall[0] = -1
		st.append((histogram[0], 0))
		i = 1
		while i < n:
			x = st.pop()
			y = histogram[i]
			while len(st) != 0 and x[0] >= y:
				x = st.pop()
			if len(st) == 0 and x[0] >= y:
				leftSmall[i] = -1
				st.append((y, i))
			else:
				st.append(x)
				st.append((y, i))
				leftSmall[i] = x[1]
			i = i + 1
		area = 0
		for i in range(n):
			area = max([area, histogram[i] * (rightSmall[i] - 1 - leftSmall[i])])
		return area


class Solution:

	def getMaxArea(self, histogram):
		stk = []
		maxArea = 0
		for i in range(0, len(histogram)):
			start = i
			while stk and stk[-1][1] > histogram[i]:
				(index, height) = stk.pop()
				maxArea = max(maxArea, (i - index) * height)
				start = index
			stk.append((start, histogram[i]))
		for i in stk:
			maxArea = max(maxArea, (len(histogram) - i[0]) * i[1])
		return maxArea


class Solution:

	def getMaxArea(self, hist):
		n = len(hist)
		stk = []
		i = 0
		max_area = 0
		while i < n:
			if not stk or hist[stk[-1]] <= hist[i]:
				stk.append(i)
				i += 1
			else:
				top = stk.pop()
				area = hist[top] * (i - (stk[-1] + 1 if stk else 0))
				max_area = max(max_area, area)
		while stk:
			top = stk.pop()
			area = hist[top] * (n - (stk[-1] + 1 if stk else 0))
			max_area = max(max_area, area)
		return max_area


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		rans = [n - 1] * n
		lans = [-1] * n
		S = []
		for i in range(n):
			while S != [] and histogram[S[-1]] > histogram[i]:
				rans[S.pop()] = i - 1
			S.append(i)
		S = []
		for i in range(n - 1, -1, -1):
			while S != [] and histogram[S[-1]] > histogram[i]:
				lans[S.pop()] = i
			S.append(i)
		ans = []
		for i in range(n):
			ans.append((rans[i] - lans[i]) * histogram[i])
		return max(ans)


class Solution:

	def getMaxArea(self, histogram):
		n = len(histogram)
		height = []
		maxArea = 0
		for (i, h) in enumerate(histogram):
			start = i
			while height and height[-1][1] > h:
				(index, hei) = height.pop()
				maxArea = max(maxArea, hei * (i - index))
				start = index
			height.append((start, h))
		for (i, h) in height:
			maxArea = max(maxArea, h * (n - i))
		return maxArea


class Solution:

	def getMaxArea(self, h):
		s = []
		res = 0
		for i in range(len(h)):
			while len(s) != 0 and h[s[-1]] >= h[i]:
				tp = s.pop()
				if len(s) == 0:
					k = i
				else:
					k = i - s[-1] - 1
				cur = h[tp] * k
				res = max(cur, res)
			s.append(i)
		while len(s) != 0:
			tp = s.pop()
			if len(s) == 0:
				k = len(h)
			else:
				k = len(h) - s[-1] - 1
			cur = h[tp] * k
			res = max(cur, res)
		return res


class Solution:

	def getMaxArea(self, histogram):
		stack = []
		left = [-1] * len(histogram)
		for i in range(len(histogram)):
			if not stack:
				left[i] = -1
			else:
				while stack and histogram[stack[-1]] >= histogram[i]:
					stack.pop()
				if not stack:
					left[i] = -1
				elif histogram[stack[-1]] < histogram[i]:
					left[i] = stack[-1]
			stack.append(i)
		stack = []
		right = [len(histogram)] * len(histogram)
		for i in range(len(histogram) - 1, -1, -1):
			if not stack:
				right[i] = len(histogram)
			else:
				while stack and histogram[stack[-1]] >= histogram[i]:
					stack.pop()
				if not stack:
					right[i] = len(histogram)
				else:
					right[i] = stack[-1]
			stack.append(i)
		max1 = 0
		for i in range(len(histogram)):
			max1 = max(max1, (right[i] - left[i] - 1) * histogram[i])
		return max1