Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed.

There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by $h[i]\:\text{where}\:i\in[1,\:n]$. If you join $\boldsymbol{\mbox{k}}$ adjacent buildings, they will form a solid rectangle of area $k\times min(h[i],h[i+1],...,h[i+k-1])$.  

Example 

$h=[3,2,3]$    

A rectangle of height $h=2$ and length $k=3$ can be constructed within the boundaries.  The area formed is $h\cdot k=2\cdot3=6$.  

Function Description

Complete the function largestRectangle int the editor below.  It should return an integer representing the largest rectangle that can be formed within the bounds of consecutive buildings.  

largestRectangle has the following parameter(s):

int h[n]: the building heights   

Returns 

- long: the area of the largest rectangle that can be formed within the bounds of consecutive buildings  

Input Format

The first line contains $n$, the number of buildings. 

The second line contains $n$ space-separated integers, each the height of a building.   

Constraints

$1\leq n\leq10^5$  
$1\leq h[i]\leq10^6$

Sample Input
STDIN       Function
-----       --------
5           h[] size n = 5
1 2 3 4 5   h = [1, 2, 3, 4, 5]

Sample Output
9

Explanation

An illustration of the test case follows.

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
def solve(H):
	(s, i, m) = ([], 0, 0)
	while i < len(H):
		if not s or H[i] > H[s[-1]]:
			s.append(i)
			i += 1
		else:
			t = s.pop()
			a = H[t] * (i - s[-1] - 1 if s else i)
			if a > m:
				m = a
	while s:
		t = s.pop()
		a = H[t] * (i - s[-1] - 1 if s else i)
		if a > m:
			m = a
	return m
N = int(input())
H = list((int(_) for _ in input().split()))
print(solve(H))


inputLength = input()
inputData = input()
data = list(map(int, inputData.split()))

def largestArea(data):
	areas = [0] * len(data)
	stack = []
	greatest = 0
	topOfStack = 0
	areaWithTop = 0
	i = 0
	while i < len(data):
		if not stack or data[stack[0]] <= data[i]:
			stack.insert(0, i)
			i += 1
		else:
			topOfStack = stack.pop(0)
			minStack = i if not stack else i - stack[0] - 1
			areaWithTop = data[topOfStack] * minStack
			greatest = areaWithTop if areaWithTop > greatest else greatest
	while stack:
		topOfStack = stack.pop(0)
		minStack = i if not stack else i - stack[0] - 1
		areaWithTop = data[topOfStack] * minStack
		greatest = areaWithTop if areaWithTop > greatest else greatest
	print(greatest)
largestArea(data)


n = int(input())
heights = [int(x) for x in input().split()]
max_area = 0
stack = [(0, len(heights) - 1)]
while stack:
	(lo, hi) = stack.pop()
	pivot = hi
	min_height = heights[hi]
	for k in range(lo, hi):
		if heights[k] < min_height:
			pivot = k
			min_height = heights[k]
	width = hi - lo + 1
	area = width * min_height
	max_area = max(area, max_area)
	if pivot > lo:
		stack.append((lo, pivot - 1))
	if pivot < hi:
		stack.append((pivot + 1, hi))
print(max_area)


N = int(input())
Hs = list(map(int, input().split()))
stack = [(0, 0)]
area = 0
for i in range(len(Hs)):
	height = Hs[i]
	(start, highest) = stack[-1]
	if highest > height:
		while highest > height:
			area = max(area, (i - start) * highest)
			stack.pop()
			prev_start = start
			(start, highest) = stack[-1]
		stack.append((prev_start, height))
	if highest < height:
		stack.append((i, height))
for remaining in stack:
	(start, height) = remaining
	area = max(area, (N - start) * height)
print(area)


def left(h, i):
	ctr = 0
	j = i - 1
	val = h[i]
	while j >= 0:
		if h[j] >= val:
			ctr += 1
		else:
			break
		j -= 1
	return ctr

def right(h, i):
	ctr = 0
	j = i + 1
	val = h[i]
	while j < len(h):
		if h[j] >= val:
			ctr += 1
		else:
			break
		j += 1
	return ctr
input()
h = [int(i) for i in input().split(' ')]
hMax = []
for i in range(0, len(h)):
	hMax.append((left(h, i) + right(h, i) + 1) * h[i])
print(max(hMax))


import sys

def solve(buildings, N):
	(min_height, idx) = min(((height, idx) for (idx, height) in enumerate(buildings)))
	current_area = N * min_height
	left_area = solve(buildings[:idx], idx) if idx else 0
	right_area = solve(buildings[idx + 1:], N - idx - 1) if idx < N - 1 else 0
	return max(left_area, current_area, right_area)
N = int(sys.stdin.readline())
buildings = [int(X) for X in sys.stdin.readline().split()]
print(solve(buildings, N))


import sys

def solve():
	(n,) = rv()
	(h,) = rl(1)
	smallertoleftindex = [-1] * n
	smallertorightindex = [n] * n
	temp = list()
	for i in range(n):
		while len(temp) > 0 and h[temp[-1]] >= h[i]:
			temp.pop(-1)
		smallertoleftindex[i] = -1 if len(temp) == 0 else temp[-1]
		temp.append(i)
	temp = list()
	for i in range(n - 1, -1, -1):
		while len(temp) > 0 and h[temp[-1]] >= h[i]:
			temp.pop(-1)
		smallertorightindex[i] = n if len(temp) == 0 else temp[-1]
		temp.append(i)
	res = 0
	for i in range(n):
		res = max(res, h[i] * (smallertorightindex[i] - smallertoleftindex[i] - 1))
	print(res)

def prt(l):
	return print(''.join(l))

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

def rl(n):
	return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
solve()


n = int(input())
nums = [int(i) for i in input().split(' ')]
nums.append(0)
l = len(nums)
height = []
idx = []
max_area = 0
for i in range(l):
	while height and height[-1] > nums[i]:
		last_height = height.pop()
		last_idx = idx.pop()
		max_area = max(last_height * (i - 1 - (idx[-1] if idx else -1)), max_area)
	height.append(nums[i])
	idx.append(i)
print(max_area)


def calc(s, H):
	top = s[-1]
	s.pop()
	return H[top] * (i if len(s) == 0 else i - s[-1] - 1)
N = int(input())
H = list(map(int, input().split()))
s = []
maxarea = 0
i = 0
while i < N:
	if len(s) == 0 or H[s[-1]] <= H[i]:
		s.append(i)
		i += 1
	else:
		maxarea = max(maxarea, calc(s, H))
while len(s) > 0:
	maxarea = max(maxarea, calc(s, H))
print(maxarea)


n = int(input())
a = [int(i) for i in input().split(' ')]
s = []
(minHt, maxArea, top) = (10000000.0, 0, -1)
for i in range(n + 1):
	while top >= 0 and (i == n or s[top][1] > a[i]):
		left = s[top - 1][0] if top > 0 else -1
		area = (i - left - 1) * s[top][1]
		if area > maxArea:
			maxArea = area
		top -= 1
		s.pop()
	if i < n:
		top += 1
		s.append([i, a[i]])
print(maxArea)

def f():
	for i in range(n):
		minHt = a[i]
		for j in range(i, n):
			if a[j] < minHt:
				minHt = a[j]
			x = (j - i + 1) * minHt
			if x > maxArea:
				maxArea = x


def get_num_left(index, array):
	num = 0
	height = array[index]
	while index > 0:
		if height > array[index - 1]:
			break
		else:
			index -= 1
			num += 1
	return num

def get_num_right(index, array):
	num = 0
	height = array[index]
	while index < len(array) - 1:
		if height > array[index + 1]:
			break
		else:
			index += 1
			num += 1
	return num

def area_rect(index, array):
	left = get_num_left(index, array)
	right = get_num_right(index, array)
	return array[index] * (left + right + 1)

def largest_area_rect(array):
	max_area = 0
	for i in range(len(array)):
		area = area_rect(i, array)
		if area > max_area:
			max_area = area
	return max_area

def main():
	N = input()
	array = [int(s) for s in input().split(' ')]
	print(largest_area_rect(array))
main()


def largestRectangeArea(height):
	stack = []
	i = 0
	maxArea = 0
	while i < len(height):
		if stack == [] or height[i] > height[stack[len(stack) - 1]]:
			stack.append(i)
		else:
			curr = stack.pop()
			width = i if stack == [] else i - stack[len(stack) - 1] - 1
			maxArea = max(maxArea, width * height[curr])
			i -= 1
		i += 1
	while stack != []:
		curr = stack.pop()
		width = i if stack == [] else len(height) - stack[len(stack) - 1] - 1
		maxArea = max(maxArea, width * height[curr])
	return maxArea

def main():
	s = input()
	data = input()
	data_input = [int(e) for e in data.split()]
	print(largestRectangeArea(data_input))
main()


stack = []
size = int(input().strip())
heights = input().strip().split(' ')
largest = 0
for i in range(0, size):
	height = int(heights[i])
	index = i
	while len(stack) > 0 and stack[-1][1] > height:
		building = stack.pop()
		largest = max(largest, building[1] * (i - building[0]))
		index = building[0]
	stack.append((index, height))
while len(stack) > 0:
	building = stack.pop()
	largest = max(largest, building[1] * (size - building[0]))
print(largest)


N = int(input())
x = input().split(' ')
h = []
ans = []
for i in range(0, N):
	h.append(int(x[i]))

def chutiyapa(x):
	right = 1
	for i in range(x + 1, N):
		if h[x] <= h[i]:
			right += 1
		else:
			break
	for i in range(x - 1, -1, -1):
		if h[x] <= h[i]:
			right += 1
		else:
			break
	return right
for i in range(0, N):
	ans.append(h[i] * chutiyapa(i))
print(max(ans))


buildings = int(input())
heights = list(map(int, input().split()))
stack = []
top = 0
current_area = 0
max_area = 0
for i in range(buildings + 1):
	if i == buildings:
		while True:
			if stack:
				top = stack.pop()
				if not stack:
					current_area = heights[top] * i
					if current_area > max_area:
						max_area = current_area
					break
				else:
					current_area = heights[top] * (i - stack[len(stack) - 1] - 1)
					if current_area > max_area:
						max_area = current_area
	elif not stack:
		stack.append(i)
	elif heights[i] >= heights[stack[len(stack) - 1]]:
		stack.append(i)
	elif heights[i] < heights[stack[len(stack) - 1]]:
		while True:
			if not stack:
				stack.append(i)
				break
			elif heights[i] >= heights[stack[len(stack) - 1]]:
				stack.append(i)
				break
			else:
				top = stack.pop()
				if not stack:
					current_area = heights[top] * i
					if current_area > max_area:
						max_area = current_area
				else:
					current_area = heights[top] * (i - stack[len(stack) - 1] - 1)
					if current_area > max_area:
						max_area = current_area
print(max_area)


def solve(H):
	(s, i, m) = ([], 0, 0)
	while i < len(H):
		if not s or H[i] > H[s[-1]]:
			s.append(i)
			i += 1
		else:
			t = s.pop()
			a = H[t] * (i - s[-1] - 1 if s else i)
			if a > m:
				m = a
	while s:
		t = s.pop()
		a = H[t] * (i - s[-1] - 1 if s else i)
		if a > m:
			m = a
	return m
N = int(input())
H = list((int(_) for _ in input().split()))
print(solve(H))


import sys
n = int(input())
hs = [int(x) for x in input().split()]
max_area = 0
for i in range(0, n):
	j = i - 1
	while j >= 0 and hs[j] > hs[i]:
		j -= 1
	k = i + 1
	while k <= n - 1 and hs[k] > hs[i]:
		k += 1
	width = k - j - 1
	area = width * hs[i]
	if area > max_area:
		max_area = area
print(max_area)


N = int(input())
height = list(map(int, input().strip().split(' ')))

def solve(xs):
	xs = [0] + xs + [0]
	stack = [0]
	res = 0
	for (i, x) in enumerate(xs):
		while x < xs[stack[-1]]:
			y = xs[stack.pop()]
			res = max(res, (i - 1 - stack[-1]) * y)
		stack.append(i)
	return res
a = solve(height)
print(a)


def rec(l):
	if len(l) == 0:
		return 0
	elif len(l) > 0:
		i = l.index(min(l))
		a = min(l) * len(l)
	if len(l) > 2:
		b = rec(l[:i])
		c = rec(l[i + 1:])
		d = max(a, b, c)
		return d
	elif i <= 2:
		return max(max(l), min(l) * len(l))
n = int(input())
a = input().split(' ')
d = []
for i in range(len(a)):
	d.append(int(a[i]))
area = rec(d)
print(area)


n = int(input())
lis = list(map(int, input().split()))
L = []
R = []
S = [(-1, -1)]
for (i, x) in enumerate(lis):
	while S[-1][0] >= x:
		S.pop()
	L.append(i - S[-1][1] - 1)
	S.append((x, i))
S = [(-1, n)]
for (i, x) in reversed(list(enumerate(lis))):
	while S[-1][0] >= x:
		S.pop()
	R.append(S[-1][1] - i - 1)
	S.append((x, i))
R = list(reversed(R))
res = 0
for i in range(n):
	res = max(res, lis[i] * (L[i] + R[i] + 1))
print(res)


def largest_rec(h, low, high):
	if low > high:
		return 0
	elif low == high:
		return h[low]
	else:
		min_ind = high
		min_val = h[high]
		for i in range(low, high):
			if h[i] < min_val:
				min_ind = i
				min_val = h[i]
		cand1 = (high - low + 1) * min_val
		cand2 = largest_rec(h, low, min_ind - 1)
		cand3 = largest_rec(h, min_ind + 1, high)
		return max(cand1, cand2, cand3)
N = int(input())
h = list(map(int, input().split()))
print(largest_rec(h, 0, N - 1))


num_houses = int(input())
heights = input().split()
houses = [0] * num_houses
for i in range(len(houses)):
	houses[i] = int(heights[i])
i = 0
left_bounds = []
max_rect = 0
while i < num_houses:
	if len(left_bounds) == 0 or houses[left_bounds[-1]] <= houses[i]:
		left_bounds.append(i)
	else:
		while len(left_bounds) > 0 and houses[left_bounds[-1]] > houses[i]:
			idx = left_bounds.pop()
			rect = houses[idx] * (i - left_bounds[-1] - 1) if len(left_bounds) > 0 else houses[idx] * i
			max_rect = rect if rect > max_rect else max_rect
		left_bounds.append(i)
	i += 1
while len(left_bounds) > 0:
	idx = left_bounds.pop()
	rect = houses[idx] * (i - left_bounds[-1] - 1) if len(left_bounds) > 0 else houses[idx] * i
	max_rect = rect if rect >= max_rect else max_rect
print(max_rect)


def largestRect(A):
	n = len(A)
	maxArea = -1
	stack = []
	i = 0
	while i < n:
		if len(stack) == 0 or A[i] >= A[stack[len(stack) - 1]]:
			stack.append(i)
			i += 1
		else:
			top = stack.pop()
			h = A[top]
			m = i if len(stack) == 0 else i - stack[len(stack) - 1] - 1
			area = h * m
			maxArea = max(maxArea, area)
	while len(stack) > 0:
		top = stack.pop()
		h = A[top]
		m = i if len(stack) == 0 else i - stack[len(stack) - 1] - 1
		area = h * m
		maxArea = max(maxArea, area)
	return maxArea
n = int(input())
A = [int(item) for item in input().split(' ')]
print(largestRect(A))


import sys
n = sys.stdin.readline()
buildings = list(map(int, sys.stdin.readline().strip().split()))
incStack = []
max_area = 0
for i in range(0, len(buildings)):
	while len(incStack) and buildings[i] <= buildings[incStack[-1]]:
		index = incStack.pop(-1)
		if len(incStack) == 0:
			current_area = i * buildings[index]
		else:
			current_area = (i - incStack[-1] - 1) * buildings[index]
		max_area = max(max_area, current_area)
	incStack.append(i)
while len(incStack) > 0:
	index = incStack.pop(-1)
	if len(incStack) == 0:
		current_area = len(buildings) * buildings[index]
	else:
		current_area = (len(buildings) - incStack[-1] - 1) * buildings[index]
	max_area = max(max_area, current_area)
print(max_area)


N = int(input())
h_gen = (int(h) for h in input().split())
max_area = 0
current_rects = []
for (h, i) in zip(h_gen, range(N)):
	if len(current_rects) == 0 or h > current_rects[-1][0]:
		current_rects.append((h, i))
	elif h == current_rects[-1][0]:
		pass
	else:
		while len(current_rects) != 0 and h < current_rects[-1][0]:
			rect = current_rects.pop()
			area = rect[0] * (i - rect[1])
			max_area = max([area, max_area])
		if len(current_rects) == 0 or h > current_rects[-1][0]:
			current_rects.append((h, rect[1]))
max_area = max([max_area, max((rect[0] * (N - rect[1]) for rect in current_rects))])
print(max_area)


def max_solid_area(h):
	stack = []
	max_area = 0
	i = 0
	while i < len(h):
		if len(stack) == 0 or h[i] >= h[stack[-1]]:
			stack.append(i)
			i = i + 1
		else:
			top = stack[-1]
			stack.pop()
			if len(stack) == 0:
				top_area = h[top] * i
			else:
				top_area = h[top] * (i - stack[-1] - 1)
			if max_area < top_area:
				max_area = top_area
	while len(stack) > 0:
		top = stack[-1]
		stack.pop()
		if len(stack) == 0:
			top_area = h[top] * i
		else:
			top_area = h[top] * (i - stack[-1] - 1)
		if max_area < top_area:
			max_area = top_area
	return max_area
(n, h) = (int(input()), list(map(int, input().split())))
print(max_solid_area(h))


N = int(input())
hist = list(map(int, input().split()))
stack = []
i = 0
max_area = 0
while i < N:
	if len(stack) == 0 or hist[stack[-1]] <= hist[i]:
		stack.append(i)
		i = i + 1
	else:
		tp = stack.pop()
		area_with_top = 0
		if len(stack) == 0:
			area_with_top = hist[tp] * i
		else:
			area_with_top = hist[tp] * (i - stack[-1] - 1)
		if max_area < area_with_top:
			max_area = area_with_top
while len(stack) != 0:
	tp = stack.pop()
	area_with_top = 0
	if len(stack) == 0:
		area_with_top = hist[tp] * i
	else:
		area_with_top = hist[tp] * (i - stack[-1] - 1)
	if max_area < area_with_top:
		max_area = area_with_top
print(max_area)


x = input()
his = input()
his = his.split()
for i in range(len(his)):
	his[i] = int(his[i])
index = []
height = []
largestarea = 0
for i in range(len(his)):
	if i == 0:
		height.append(his[i])
		index.append(i)
	elif his[i] > height[-1]:
		height.append(his[i])
		index.append(i)
	elif his[i] < height[len(height) - 1]:
		lastindex = 0
		while height != [] and his[i] < height[len(height) - 1]:
			lastindex = index.pop()
			area = height.pop() * (i - lastindex)
			largestarea = max(area, largestarea)
		height.append(his[i])
		index.append(lastindex)
while height != []:
	area = height.pop() * (len(his) - index.pop())
	largestarea = max(area, largestarea)
print(largestarea)


import sys
N = int(input())
heights = [int(i) for i in input().split()]
stack = []
max_area = 0
area = 0
top = 0
i = 0
while i < N:
	if not stack or heights[stack[len(stack) - 1]] < heights[i]:
		stack.append(i)
		i += 1
	else:
		top = stack.pop()
		if not stack:
			area = heights[top] * i
		else:
			area = heights[top] * (i - stack[len(stack) - 1] - 1)
		if area > max_area:
			max_area = area
while stack:
	top = stack.pop()
	if not stack:
		area = heights[top] * i
	else:
		area = heights[top] * (i - stack[len(stack) - 1] - 1)
	if area > max_area:
		max_area = area
print(max_area)


def sliceAndCalcBySmaller(array, greater):
	smaller = min(array)
	lenght = len(array)
	index = array.index(smaller)
	if smaller * lenght > greater:
		greater = smaller * lenght
	firstPart = array[:index]
	secondPart = array[index + 1:]
	if len(firstPart) > 0:
		greater = sliceAndCalcBySmaller(firstPart, greater)
	if len(secondPart) > 0:
		greater = sliceAndCalcBySmaller(secondPart, greater)
	return greater
n = input()
builds = [int(i) for i in input().split()]
print(sliceAndCalcBySmaller(builds, 0))


N = int(input())
buildings = [int(x) for x in input().split()]
stack = []
max_rect = 0
for (i, building) in enumerate(buildings):
	if not stack:
		stack.append([building, 0])
	elif building >= stack[-1][0]:
		stack.append([building, 0])
	else:
		num_removed = 0
		while stack and building < stack[-1][0]:
			removed_building = stack.pop()
			num_removed += 1 + removed_building[1]
			max_rect = max(max_rect, removed_building[0] * num_removed)
		stack.append([building, num_removed])
num_removed = 0
while stack:
	removed_building = stack.pop()
	num_removed += 1 + removed_building[1]
	max_rect = max(max_rect, removed_building[0] * num_removed)
print(max_rect)


N = input()
H = [int(i) for i in input().split()]
queue = []
queue = [(0, len(H))]
result = -1
while len(queue) != 0:
	elem = queue.pop(0)
	begin = elem[0]
	end = elem[1]
	min_h = min(H[begin:end])
	area = min_h * (end - begin)
	result = max(area, result)
	offset = H[begin:end].index(min_h)
	if offset > 0:
		queue.append((begin, begin + offset))
	if begin + offset < end - 1:
		queue.append((begin + offset + 1, end))
print(result)


import fileinput

class Stack:

	def __init__(self):
		self.items = []

	def push(self, item):
		self.items.append(item)

	def pop(self):
		return self.items.pop()

	def isEmpty(self):
		return self.items == []

	def empty(self):
		self.items = []

	def topOfStack(self):
		return len(self.items)

	def top(self):
		return self.items[len(self.items) - 1]

	def __str__(self):
		return str(self.items)

def main(hist, n):
	s = Stack()
	max_area = 0
	tp = None
	area_with_top = 0
	i = 0
	while i < n:
		if s.isEmpty() or hist[s.top()] <= hist[i]:
			s.push(i)
			i += 1
		else:
			tp = s.top()
			s.pop()
			area_with_top = hist[tp] * (i if s.isEmpty() else i - s.top() - 1)
			if max_area < area_with_top:
				max_area = area_with_top
	while s.isEmpty() == False:
		tp = s.top()
		s.pop()
		area_with_top = hist[tp] * (i if s.isEmpty() else i - s.top() - 1)
		if max_area < area_with_top:
			max_area = area_with_top
	print(max_area)
	return max_area
myHist = None
myN = None
for line in fileinput.input():
	if myN is None:
		myN = line
	else:
		myHist = line
list = map(int, myHist.split(' '))
myHist = []
for item in list:
	myHist.append(item)
main(myHist, int(myN))


def solve(H):
	(s, i, m) = ([], 0, 0)
	while i < len(H):
		if not s or H[i] > H[s[-1]]:
			s.append(i)
			i += 1
		else:
			t = s.pop()
			a = H[t] * (i - s[-1] - 1 if s else i)
			if a > m:
				m = a
	while s:
		t = s.pop()
		a = H[t] * (i - s[-1] - 1 if s else i)
		if a > m:
			m = a
	return m
N = int(input())
H = list((int(_) for _ in input().split()))
print(solve(H))


stack = []
n = int(input())
buildings = [int(x) for x in input().split()]
max_so_far = 0
index = 0
while index < n:
	if len(stack) == 0 or buildings[index] >= buildings[stack[0]]:
		stack.insert(0, index)
		index += 1
	else:
		right_index = index
		height = buildings[stack[0]]
		stack.pop(0)
		left_index = 0 if len(stack) == 0 else stack[0] + 1
		area = (right_index - left_index) * height
		max_so_far = area if area > max_so_far else max_so_far
while len(stack) > 0:
	right_index = index
	height = buildings[stack[0]]
	stack.pop(0)
	left_index = 0 if len(stack) == 0 else stack[0] + 1
	area = (right_index - left_index) * height
	max_so_far = area if area > max_so_far else max_so_far
print(max_so_far)


def largestRectangle(A):
	stack = []
	maxArea = 0
	area = 0
	i = 0
	while i < len(A):
		if not stack or A[stack[-1]] <= A[i]:
			stack.append(i)
			i = i + 1
		else:
			top = stack.pop()
			if not stack:
				area = A[top] * i
			else:
				area = A[top] * (i - stack[-1] - 1)
			if area > maxArea:
				maxArea = area
	while stack:
		top = stack.pop()
		if not stack:
			area = A[top] * i
		else:
			area = A[top] * (i - stack[-1] - 1)
		if area > maxArea:
			maxArea = area
	return maxArea
n = int(input())
A = list(map(int, input().split()))
print(largestRectangle(A))


__author__ = 'Siddharth'

def foo(A):
	if not A:
		return 0
	elif len(A) == 1:
		return A[0]
	amin = min(A)
	w = len(A)
	R = amin * w
	index = A.index(amin)
	X = A[:index]
	Y = A[index + 1:]
	return max(R, foo(X), foo(Y))
N = int(input())
A = list(map(int, input().split()))
print(foo(A))


num_buildings = int(input())
stack = []
maximum = 0
buildings = [int(num) for num in input().split(' ')]
buildings.append(0)
for (index, current_num) in enumerate(buildings):
	if len(stack) == 0 or buildings[stack[-1]] <= current_num:
		stack.append(index)
	else:
		while len(stack) > 0 and buildings[stack[-1]] > current_num:
			top_index = stack.pop()
			if len(stack) == 0:
				maximum = max(maximum, buildings[top_index] * index)
			else:
				maximum = max(maximum, buildings[top_index] * (index - stack[-1] - 1))
		stack.append(index)
print(maximum)


building_count = int(input())
buildings = [int(x) for x in input().split(' ')]

def largestRectangleArea(height):
	maxArea = 0
	stackHeight = []
	stackIndex = []
	for i in range(len(height)):
		if stackHeight == [] or height[i] > stackHeight[len(stackHeight) - 1]:
			stackHeight.append(height[i])
			stackIndex.append(i)
		elif height[i] < stackHeight[len(stackHeight) - 1]:
			lastIndex = 0
			while stackHeight and height[i] < stackHeight[len(stackHeight) - 1]:
				lastIndex = stackIndex.pop()
				tempArea = stackHeight.pop() * (i - lastIndex)
				if maxArea < tempArea:
					maxArea = tempArea
			stackHeight.append(height[i])
			stackIndex.append(lastIndex)
	while stackHeight:
		tempArea = stackHeight.pop() * (len(height) - stackIndex.pop())
		if tempArea > maxArea:
			maxArea = tempArea
	return maxArea
print(largestRectangleArea(buildings))


n = int(input())
bldgs = [int(x) for x in input().split()]
best = -1
for i in range(len(bldgs)):
	start = i
	while start > 0 and bldgs[start - 1] >= bldgs[i]:
		start -= 1
	end = i
	while end < len(bldgs) - 1 and bldgs[end + 1] >= bldgs[i]:
		end += 1
	this = (end - start + 1) * bldgs[i]
	best = max(best, this)
print('{}'.format(best))


N = int(input())
heights = [int(x) for x in input().strip().split(' ')]
heights.append(0)
currH = 0
blocks = []
maxSurface = 0
for x in range(len(heights)):
	h = heights[x]
	if h > currH:
		blocks.append((x, h))
	else:
		cb = (-1, -1)
		while len(blocks) > 0 and blocks[-1][1] >= h:
			cb = blocks.pop()
			ch = cb[1]
			w = x - cb[0]
			surface = w * ch
			maxSurface = max(maxSurface, surface)
		if h > 0:
			blocks.append((cb[0], h))
	currH = h
print(maxSurface)


import sys
data = sys.stdin.readlines()

def area(i, items):
	start = i
	end = i
	while start > 0:
		if items[start - 1] < items[i]:
			break
		else:
			start -= 1
	while end < len(items) - 1:
		if items[end + 1] < items[i]:
			break
		else:
			end += 1
	total = end - start + 1
	return total * items[i]
items = [int(i) for i in data[1].strip().split()]
max = 0
for i in range(0, len(items)):
	c = area(i, items)
	if c > max:
		max = c
print(max)


N = int(input())
hist = [int(i) for i in input().split()]

def stack_based(hist, N):
	s = []
	max_area = 0
	i = 0
	while i < N:
		if not s or hist[s[-1]] <= hist[i]:
			s.append(i)
			i += 1
		else:
			tp = s.pop()
			area_with_top = hist[tp] * (i if not s else i - s[-1] - 1)
			if max_area < area_with_top:
				max_area = area_with_top
	while s:
		tp = s.pop()
		area_with_top = hist[tp] * (i if not s else i - s[-1] - 1)
		if max_area < area_with_top:
			max_area = area_with_top
	return max_area
print(stack_based(hist, N))


input()
l = list(map(int, input().split()))
max = len(l)
p = 0
s = []
while p < len(l):
	if len(s) == 0 or l[p] >= l[s[-1]]:
		s.append(p)
		p += 1
	else:
		a = l[s.pop()] * (p if len(s) == 0 else p - s[-1] - 1)
		if a > max:
			max = a
while len(s) > 0:
	a = l[s.pop()] * (p if len(s) == 0 else p - s[-1] - 1)
	if a > max:
		max = a
print(max)


def findAns(arr):
	citySize = len(arr)
	for i in range(citySize):
		arr[i] = int(arr[i])
	stack = []
	for i in range(citySize):
		stackSize = len(stack)
		lowestIndex = i
		for j in range(stackSize):
			values = stack[stackSize - 1 - j]
			if values[0] > arr[i]:
				if values[2] > i - 1:
					values[2] = i - 1
				if lowestIndex > values[1]:
					lowestIndex = values[1]
			else:
				break
		stack.append([arr[i], lowestIndex, citySize - 1])
	maxVal = 0
	for i in range(len(stack)):
		val = stack[i]
		currentMax = val[0] * (val[2] - val[1] + 1)
		if currentMax > maxVal:
			maxVal = currentMax
	return maxVal
numberOfElements = input()
arr = input().split(' ')
print(findAns(arr))


n = int(input())
data = list(map(int, input().split()))
s = []
max_area = 0
for i in range(len(data)):
	while len(s) and data[i] < data[s[-1]]:
		j = s.pop()
		area = data[j] * (i - s[-1] - 1) if len(s) else data[j] * i
		max_area = max(max_area, area)
	s.append(i)
i = len(data)
while len(s):
	j = s.pop()
	area = data[j] * (i - s[-1] - 1) if len(s) else data[j] * i
	max_area = max(max_area, area)
print(max_area)


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

def getArea(indexStack, i):
	height = l[indexStack.pop()]
	width = i
	if len(indexStack) > 0:
		width = i - indexStack[-1] - 1
	return height * width
indexStack = []
area = 0
for i in range(len(l)):
	while len(indexStack) > 0 and l[i] < l[indexStack[-1]]:
		area = max(area, getArea(indexStack, i))
	indexStack.append(i)
while len(indexStack) > 0:
	area = max(area, getArea(indexStack, len(l)))
print(area)


n = int(input())
lst = [int(x) for x in input().split(' ')]

def large_width(lst):
	if len(lst) == 1:
		return lst[0]
	elif len(lst) == 0:
		return 0
	smallest = (-1, -1)
	for (i, x) in enumerate(lst):
		if x < smallest[1] or smallest[1] == -1:
			smallest = (i, x)
	center = len(lst) * smallest[1]
	left = large_width(lst[:smallest[0]])
	right = large_width(lst[smallest[0] + 1:])
	if left < right:
		if right < center:
			return center
		else:
			return right
	elif left < center:
		return center
	else:
		return left
print(large_width(lst))


n = int(input())
heights = [int(x) for x in input().split(' ')]
assert len(heights) == n
stack = []
result = 0
heights.insert(0, 0)
heights.append(0)
for (x, h) in enumerate(heights):
	while stack and h < stack[-1][1]:
		(back_x, back_h) = stack.pop()
		result = max(result, back_h * (x - stack[-1][0] - 1))
	stack.append((x, h))
print(result)


n = int(input())
arr = [int(x) for x in input().split()]
l = len(arr)
max = 0
s = []
i = 0
while i < n:
	if not s or arr[i] >= arr[s[-1]]:
		s.append(i)
		i += 1
	else:
		top = s.pop()
		if not s:
			area = arr[top] * i
		else:
			area = arr[top] * (i - 1 - s[-1])
		if area > max:
			max = area
while s:
	top = s.pop()
	if not s:
		area = arr[top] * i
	else:
		area = arr[top] * (i - 1 - s[-1])
		if area > max:
			max = area
print(max)


import sys
for line in sys.stdin:
	stack = [int(n) for n in line.split()]

def max_stack_area(stack):
	if not stack:
		return 0
	else:
		return min(stack) * len(stack)

def calc_area(stack, areas):
	if len(stack) > 1:
		areas.append(max_stack_area(stack))
		mid_point = stack.index(min(stack))
		calc_area(stack[0:mid_point], areas)
		calc_area(stack[mid_point + 1:len(stack)], areas)
	else:
		pass
areas = []
calc_area(stack, areas)
print(max(areas))


N = int(input())
heights = [int(x) for x in input().split()]
maxh = 0
for (i, h) in enumerate(heights):
	i1 = i2 = 0
	for j in range(i):
		i1 = i - j - 1
		if heights[i1] < h:
			i1 += 1
			break
	for i2 in range(i + 1, N):
		if heights[i2] < h:
			if i2 > 0:
				i2 -= 1
			break
	maxh = max((i2 - i1 + 1) * h, maxh)
print(maxh)


def calculate(heights):
	result = 0
	for (index, value) in enumerate(heights):
		current = value
		(left, right) = (index - 1, index + 1)
		while left >= 0 and heights[left] >= value:
			current += value
			left -= 1
		while right < len(heights) and heights[right] >= value:
			current += value
			right += 1
		if current > result:
			result = current
	return result

def actions():
	while True:
		yield input()
go = actions()
N = int(next(go))
print(calculate([int(i) for i in next(go).split()][::-1]))


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

def largest_rectangle(heights, from_idx, to_idx):
	if from_idx > to_idx:
		return -1
	elif from_idx == to_idx:
		return heights[from_idx]
	min_height = heights[from_idx]
	min_index = from_idx
	for i in range(from_idx + 1, to_idx + 1):
		if heights[i] < min_height:
			min_height = heights[i]
			min_index = i
	return max(largest_rectangle(heights, from_idx, min_index - 1), min_height * (to_idx - from_idx + 1), largest_rectangle(heights, min_index + 1, to_idx))
print(largest_rectangle(heights, 0, n - 1))


n = int(input())
ar = input().strip().split()
ar = [int(e) for e in ar]
ma = 0
for i in range(n):
	j_1 = i
	j_2 = i
	while j_1 + 1 < n and ar[j_1 + 1] > ar[i]:
		j_1 += 1
	while j_2 - 1 >= 0 and ar[j_2 - 1] > ar[i]:
		j_2 -= 1
	c = ar[i] * (j_1 - j_2 + 1)
	if ma < c:
		ma = c
print(ma)


from itertools import takewhile, chain
from collections import deque
n = int(input())
b = deque(map(int, input().split()))
a = deque()
m = 0
for i in range(len(b)):
	streak = lambda x: x >= b[0]
	m = max(m, sum((b[0] for _ in chain(takewhile(streak, b), takewhile(streak, a)))))
	a.appendleft(b.popleft())
print(m)


from itertools import takewhile, chain
from collections import deque
n = int(input())
b = deque(map(int, input().split()))
a = deque()
m = 0
for i in range(len(b)):
	streak = lambda x: x >= b[0]
	m = max(m, sum((b[0] for _ in chain(takewhile(streak, b), takewhile(streak, a)))))
	a.appendleft(b.popleft())
print(m)


N = int(input().strip())
b = [int(_) for _ in input().strip().split()]
max_rec = 0
for i in range(N):
	rec = b[i]
	left = i - 1
	while left >= 0:
		if b[left] < b[i]:
			break
		else:
			rec += b[i]
		left -= 1
	right = i + 1
	while right < N:
		if b[right] < b[i]:
			break
		else:
			rec += b[i]
		right += 1
	max_rec = max(max_rec, rec)
print(max_rec)


n = int(input())
a = list(map(int, input().strip().split(' ')))
stack = []
i = 0
top = 0
max = 0
maxArea = 0
while i < len(a):
	if len(stack) < 1:
		stack.append(i)
	elif a[stack[len(stack) - 1]] <= a[i]:
		stack.append(i)
	else:
		while len(stack) > 0 and a[stack[len(stack) - 1]] > a[i]:
			top = stack.pop()
			if len(stack) < 1:
				area = a[top] * i
			else:
				area = a[top] * (i - stack[len(stack) - 1] - 1)
			if area > maxArea:
				maxArea = area
		stack.append(i)
	i += 1
while stack:
	top = stack.pop()
	if len(stack) < 1:
		area = a[top] * i
	else:
		area = a[top] * (i - stack[len(stack) - 1] - 1)
	if area > maxArea:
		maxArea = area
print(maxArea)


def histogram_largest_rectangle(hist):

	def check_top():
		nonlocal max_area
		top_value = hist[stack.pop()]
		current_area = top_value * i if not stack else top_value * (i - stack[-1] - 1)
		if current_area > max_area:
			max_area = current_area
	stack = []
	max_area = 0
	i = 0
	n = len(hist)
	while i < n:
		if not stack or hist[stack[-1]] <= hist[i]:
			stack.append(i)
			i += 1
		else:
			check_top()
	while stack:
		check_top()
	return max_area
n = int(input())
arr = [int(x) for x in input().split()]
print(histogram_largest_rectangle(arr))


from itertools import takewhile, chain
from collections import deque
n = int(input())
b = deque(map(int, input().split()))
a = deque()
m = 0
for i in range(len(b)):
	streak = lambda x: x >= b[0]
	m = max(m, sum((b[0] for _ in chain(takewhile(streak, b), takewhile(streak, a)))))
	a.appendleft(b.popleft())
print(m)


def runn():
	counts = []
	greatest_area = int(input())
	heights = []
	recs = [int(x) for x in input().split()]
	counts.append(0)
	counts.append(1)
	heights.append(recs.pop())
	while len(recs) > 0:
		curr = recs.pop()
		if len(heights) == 0:
			counts.append(1)
			heights.append(curr)
		elif curr > heights[-1]:
			counts.append(1)
			heights.append(curr)
		elif curr < heights[-1]:
			last_height = heights.pop()
			last_count = counts.pop()
			area = last_count * last_height
			if area > greatest_area:
				greatest_area = area
			if len(heights) > 0 and curr < heights[-1]:
				while len(heights) > 0 and curr < heights[-1]:
					last_height = heights.pop()
					last_count += counts.pop()
					area = last_count * last_height
					if area > greatest_area:
						greatest_area = area
				if len(counts) > 0:
					counts.append(last_count + 1)
				else:
					counts[-1] += last_count + 1
			elif len(heights) > 0:
				counts.append(last_count + 1)
			else:
				counts.append(last_count + 1)
			heights.append(curr)
		else:
			counts[-1] += 1
	while len(heights) > 0:
		curr_count = counts.pop()
		area = heights.pop() * curr_count
		if area > greatest_area:
			greatest_area = area
		if len(counts) > 0:
			counts[-1] += curr_count
		else:
			counts.append(curr_count)
	print(str(greatest_area))
runn()


def maxArea(b):
	s = []
	n = len(b)
	rec = [0] * n
	for i in range(len(b)):
		while len(s) > 0 and b[s[-1]] > b[i]:
			t = s.pop()
			rec[t] = i
		s.append(i)
	for i in s:
		rec[i] = n
	return rec
temp = input()
b = [int(i) for i in input().split()]
n = len(b)
rec1 = maxArea(b)
rec2 = maxArea(b[::-1])[::-1]
maxA = 0
for i in range(n):
	new = b[i] * (rec1[i] + rec2[i] - n)
	maxA = max(new, maxA)
print(maxA)


class ArrayStack(object):

	def __init__(self):
		self._data = []

	def __len__(self):
		return len(self._data)

	def push(self, item):
		self._data.append(item)

	def is_empty(self):
		return len(self._data) == 0

	def top(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data[-1]

	def pop(self):
		if self.is_empty():
			raise Empty('stack is empty')
		return self._data.pop()

def largest_rectangle(hist):
	n = len(hist)
	i = 0
	max_area = 0
	s = ArrayStack()
	while i < n:
		if s.is_empty() or hist[s.top()] <= hist[i]:
			s.push(i)
			i += 1
		else:
			top = s.top()
			s.pop()
			area_with_top = hist[top] * (i if s.is_empty() else i - s.top() - 1)
			max_area = max(max_area, area_with_top)
	while not s.is_empty():
		top = s.top()
		s.pop()
		area_with_top = hist[top] * (i if s.is_empty() else i - s.top() - 1)
		max_area = max(max_area, area_with_top)
	return max_area
try:
	n = int(input())
except ValueError:
	print('Not a number')
hist = [int(i) for i in input().split()]
print(largest_rectangle(hist))


from itertools import takewhile, chain
from collections import deque
n = int(input())
b = deque(map(int, input().split()))
a = deque()
m = 0
for i in range(len(b)):
	streak = lambda x: x >= b[0]
	m = max(m, sum((b[0] for _ in chain(takewhile(streak, b), takewhile(streak, a)))))
	a.appendleft(b.popleft())
print(m)


N = int(input())
h = list(map(int, input().split()))
res = -1
stack = []
i = 0
while i < N:
	if not stack or h[stack[-1]] <= h[i]:
		stack.append(i)
		i += 1
	else:
		index = stack.pop()
		area = h[index] * (i if not stack else i - stack[-1] - 1)
		res = max(res, area)
while stack:
	index = stack.pop()
	area = h[index] * (i if not stack else i - stack[-1] - 1)
	res = max(res, area)
print(res)


N = int(input())
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
stack = []
maxarea = 0
i = 0
while i < N:
	if len(stack) == 0 or arr[stack[-1]] <= arr[i]:
		stack.append(i)
		i += 1
	else:
		top = stack.pop()
		areatopbar = arr[top] * (i if len(stack) == 0 else i - stack[-1] - 1)
		if maxarea < areatopbar:
			maxarea = areatopbar
while len(stack) != 0:
	top = stack.pop()
	areatopbar = arr[top] * (i if len(stack) == 0 else i - stack[-1] - 1)
	if maxarea < areatopbar:
		maxarea = areatopbar
print(maxarea)


def computeLargestArea(hist, N):
	stack = []
	max_area = 0
	idx = 0
	while idx < N:
		if not stack or hist[stack[-1]] <= hist[idx]:
			stack.append(idx)
			idx = idx + 1
		else:
			height_idx = stack.pop()
			depth = idx
			if stack:
				depth = idx - stack[-1] - 1
			area = hist[height_idx] * depth
			max_area = max(area, max_area)
	while stack:
		height_idx = stack.pop()
		depth = idx
		if stack:
			depth = idx - stack[-1] - 1
		area = hist[height_idx] * depth
		max_area = max(area, max_area)
	return max_area
N = int(input())
hist = list(map(int, input().split()))
print(computeLargestArea(hist, N))


class Stack:

	def __init__(self):
		self.items = []

	def is_empty(self):
		return self.items == []

	def push(self, item):
		self.items.append(item)

	def pop(self):
		return self.items.pop()

	def peek(self):
		return self.items[-1]

	def size(self):
		return len(self.items)

def highest_area():
	n = int(input().strip())
	max_area = 0
	heights = list(map(int, input().strip().split()))
	s = Stack()
	i = 0
	while i < n:
		if s.is_empty() or heights[i] >= heights[s.peek()]:
			s.push(i)
			i += 1
		else:
			top = s.pop()
			if s.is_empty():
				next_top = -1
			else:
				next_top = s.peek()
			area_top_min = heights[top] * (i - next_top - 1)
			max_area = max(area_top_min, max_area)
	while not s.is_empty():
		top = s.pop()
		if s.is_empty():
			next_top = -1
		else:
			next_top = s.peek()
		max_area = max(max_area, heights[top] * (i - next_top - 1))
	return max_area
print(highest_area())


n = int(input())
hist = list(map(int, input().strip().split(' ')))
s = []
max_area = 0
i = 0
while i < n:
	if len(s) == 0 or hist[s[-1]] <= hist[i]:
		s.append(i)
		i += 1
	else:
		tp = s[-1]
		s.pop()
		if len(s) == 0:
			term = i
		else:
			term = i - s[-1] - 1
		area_with_top = hist[tp] * term
		if max_area < area_with_top:
			max_area = area_with_top
while len(s) > 0:
	tp = s[-1]
	s.pop()
	if len(s) == 0:
		term = i
	else:
		term = i - s[-1] - 1
	area_with_top = hist[tp] * term
	if max_area < area_with_top:
		max_area = area_with_top
print(max_area)


N = int(input())
heights = [int(i) for i in input().split()]
stack = []
max_area = -1
i = 0
while i < len(heights):
	h = heights[i]
	if not stack or h >= heights[stack[-1]]:
		stack.append(i)
		i += 1
	else:
		top = stack.pop()
		if not stack:
			width = i
		else:
			width = i - stack[-1] - 1
		max_area = max(heights[top] * width, max_area)
while stack:
	top = stack.pop()
	if not stack:
		width = i
	else:
		width = i - stack[-1] - 1
	max_area = max(heights[top] * width, max_area)
print(max_area)


class LargestRectangleFinder:

	def __init__(self, buildings):
		self.largest_area = 0
		self.buildings = buildings
		self.increasing_sequence = []

	def _sequence_is_empty(self):
		return not self.increasing_sequence

	def _is_drop_in_height(self, height):
		return height < self.buildings[self.increasing_sequence[-1]]

	def _calculate_area(self, index_of_building, current_index):
		height = self.buildings[index_of_building]
		if self._sequence_is_empty():
			return height * current_index
		index_of_last_smaller_building = self.increasing_sequence[-1]
		return (current_index - index_of_last_smaller_building - 1) * height

	def find_largest_area(self):
		for (index, height) in enumerate(self.buildings):
			if self._sequence_is_empty() or not self._is_drop_in_height(height):
				self.increasing_sequence.append(index)
			else:
				while not self._sequence_is_empty() and self._is_drop_in_height(height):
					index_of_building_to_calc = self.increasing_sequence.pop()
					area = self._calculate_area(index_of_building=index_of_building_to_calc, current_index=index)
					if area > self.largest_area:
						self.largest_area = area
				self.increasing_sequence.append(index)
		while self.increasing_sequence:
			index_of_building_to_calc = self.increasing_sequence.pop()
			area = self._calculate_area(index_of_building=index_of_building_to_calc, current_index=len(self.buildings))
			if area > self.largest_area:
				self.largest_area = area
		return self.largest_area
input_text = input()
input_text = input()
buildings = input_text.split(' ')
buildings = [int(x) for x in buildings]
finder = LargestRectangleFinder(buildings=buildings)
print(finder.find_largest_area())


def solve(h, N):
	(stack, i, max_area) = ([], 0, 0)
	while i < N:
		if not stack or h[stack[-1]] <= h[i]:
			stack.append(i)
			i += 1
		else:
			(i_h, width) = (stack.pop(), i - (stack[-1] + 1) if stack else i)
			area = h[i_h] * width
			max_area = max(area, max_area)
	while stack:
		(i_h, width) = (stack.pop(), i - (stack[-1] + 1) if stack else i)
		area = h[i_h] * width
		max_area = max(area, max_area)
	return max_area
(N, h) = (int(input()), [int(x) for x in input().split()])
print(solve(h, N))


N = int(input())
h = list(map(int, input().split()))
maxH = 0
for i in range(N):
	left = 0
	right = N - 1
	for j in range(i, -1, -1):
		if h[j] < h[i]:
			left = j + 1
			break
	for k in range(i, N):
		if h[k] < h[i]:
			right = k - 1
			break
	base = right - left + 1
	area = h[i] * base
	maxH = max(maxH, area)
print(maxH)


def findIMin(l):
	return min(range(len(l)), key=l.__getitem__)

def findMaxRec(h):
	if len(h) == 1:
		return h[0]
	i = findIMin(h)
	if i == 0:
		return max(h[i] * len(h), findMaxRec(h[i + 1:]))
	if i == len(h) - 1:
		return max(h[i] * len(h), findMaxRec(h[:i]))
	return max(h[i] * len(h), findMaxRec(h[:i]), findMaxRec(h[i + 1:]))
n = int(input())
h = list(map(int, input().split()))
print(findMaxRec(h))


def index_min(values, lo, hi):
	return min(range(lo, hi + 1), key=values.__getitem__)

def find_area(arr, lo, hi):
	if lo < hi:
		min_index = index_min(arr, lo, hi)
		return max(arr[min_index] * (hi - lo + 1), find_area(arr, lo, max(lo, min_index - 1)), find_area(arr, min(min_index + 1, hi), hi))
	else:
		return arr[lo]
n = int(input())
arr = [int(x) for x in input().split()]
print(find_area(arr, 0, n - 1))


def maxi(array):
	res = 0
	for i in range(len(array)):
		right = 0
		j = i + 1
		while j < len(array) and array[j] >= array[i]:
			right += 1
			j += 1
		left = 0
		j = i - 1
		while j >= 0 and array[j] >= array[i]:
			left += 1
			j -= 1
		res = max(res, (left + right + 1) * array[i])
	return res
n = int(input())
array = list(map(int, input().split()))
print(maxi(array))


import sys
length = int(sys.stdin.readline())
buildings = [int(num) for num in sys.stdin.readline().split()]

def find_buildings_left(idx, h):
	while idx > 0 and buildings[idx - 1] >= h:
		idx -= 1
	return idx

def find_buildings_right(idx, h):
	while idx < length - 1 and buildings[idx + 1] >= h:
		idx += 1
	return idx

def find_area(idx):
	h = buildings[idx]
	left = find_buildings_left(idx, h)
	right = find_buildings_right(idx, h)
	return (right - left + 1) * h
val = 0
for i in range(0, length):
	val = max(val, find_area(i))
print(val)


n = int(input())
h = [int(x) for x in input().split()]
max_area = 0
stack = []
i = 0
while i < n:
	if not stack or h[stack[-1]] <= h[i]:
		stack.append(i)
		i += 1
	else:
		tp = stack[-1]
		stack.pop()
		area = h[tp] * (i - stack[-1] - 1 if stack else i)
		if area > max_area:
			max_area = area
while stack:
	tp = stack[-1]
	stack.pop()
	area = h[tp] * (i - stack[-1] - 1 if stack else i)
	if area > max_area:
		max_area = area
print(max_area)


N_BUILDINGS = int(input())
BUILDINGS = [int(i) for i in input().split()]
stack = [0]
area = 0
maxArea = -1
top = BUILDINGS[0]
i = 1
while i < N_BUILDINGS:
	while len(stack) > 0 and BUILDINGS[i] < BUILDINGS[stack[-1]]:
		if len(stack) > 0:
			top = stack.pop()
			if len(stack) == 0:
				area = BUILDINGS[top] * i
			else:
				area = BUILDINGS[top] * (i - stack[-1] - 1)
			maxArea = max(area, maxArea)
	stack.append(i)
	i += 1
while len(stack) > 0:
	top = stack.pop()
	if len(stack) == 0:
		area = BUILDINGS[top] * i
	else:
		area = BUILDINGS[top] * (i - stack[-1] - 1)
	maxArea = max(area, maxArea)
print(maxArea)


N = int(input())
height = [int(x) for x in input().split()]
Max = 0
for i in range(N):
	current = i
	while current > 0:
		if height[current - 1] >= height[i]:
			current -= 1
		else:
			break
	low = current
	current = i
	while current < N - 1:
		if height[current + 1] >= height[i]:
			current += 1
		else:
			break
	high = current
	if Max < height[i] * (high - low + 1):
		Max = height[i] * (high - low + 1)
print(Max)


class Stack:

	def __init__(self):
		self.items = []

	def isEmpty(self):
		return self.items == []

	def push(self, element):
		self.items.append(element)

	def pop(self):
		return self.items.pop()

	def size(self):
		return len(self.items)

	def peek(self):
		return self.items[len(self.items) - 1]

class DataNode:

	def __init__(self, val, ind):
		self.value = val
		self.ind = ind
n = int(input().strip())
h = [int(temp) for temp in input().strip().split(' ')]
maxArea = 0
area = 0
top = None
ind = 0
stack = Stack()
stacki = 0
last_i = 0
for i in range(n):
	if not stack.isEmpty():
		if h[i] <= stack.peek().value:
			while h[i] <= stack.peek().value:
				top = stack.pop()
				ind = top.ind
				if stack.isEmpty():
					stacki = 0
					area = top.value * i
				else:
					stacki = stack.peek().ind
					area = top.value * (i - stacki - 1)
				if area > maxArea:
					maxArea = area
				if stack.isEmpty():
					break
			stack.push(DataNode(h[i], i))
		else:
			stack.push(DataNode(h[i], i))
	else:
		stack.push(DataNode(h[i], i))
	last_i = i
while 1:
	top = stack.pop()
	if stack.isEmpty():
		area = top.value * (last_i + 1)
		if area > maxArea:
			maxArea = area
		break
	else:
		if stack.isEmpty():
			stacki = 0
		else:
			stacki = stack.peek().ind
		area = top.value * (last_i - stacki)
		if area > maxArea:
			maxArea = area
print(maxArea)


N = int(input())
b = [int(s) for s in str.split(input())]
height = [[0, 0]]
max_area = 0
for i in range(0, N):
	if b[i] > height[-1][0]:
		height.append([b[i], i])
	elif b[i] < height[-1][0]:
		cur_i = i
		while b[i] < height[-1][0]:
			area = height[-1][0] * (i - height[-1][1])
			max_area = max(max_area, area)
			cur_i = height[-1][1]
			height.pop()
		if b[i] > height[-1][0]:
			height.append([b[i], cur_i])
while len(height) > 0:
	area = height[-1][0] * (N - height[-1][1])
	max_area = max(max_area, area)
	height.pop()
print(max_area)


N = int(input())

def largest_rectangle(heights):
	stack = []
	max_area = -1
	n = len(heights)
	i = 0
	while i < n:
		if not stack or heights[stack[-1]] <= heights[i]:
			stack.append(i)
			i += 1
		else:
			top = stack.pop()
			width = i if not stack else i - stack[-1] - 1
			area = heights[top] * width
			max_area = max(max_area, area)
	while stack:
		top = stack.pop()
		width = n if not stack else n - stack[-1] - 1
		area = heights[top] * width
		max_area = max(max_area, area)
	return max_area
heights = tuple(map(int, input().split()))
print(largest_rectangle(heights))


import itertools

def remove_until_elem(stack, elem, index):
	_max = 0
	while True:
		if stack[-1][0] <= elem:
			stack.append((elem, index))
			break
		(area_h, _) = stack.pop()
		area_left = stack[-1][1]
		area_w = index - area_left - 1
		area = area_w * area_h
		_max = max(_max, area)
	return _max

def solve(hs):
	if not hs:
		return 0
	stack = [(0, -1)]
	_max = 0
	hs.append(0)
	for (index, elem) in enumerate(hs):
		if stack[-1][0] <= elem:
			stack.append((elem, index))
		else:
			_max = max(remove_until_elem(stack, elem, index), _max)
	return _max
_ = int(input())
hs = [int(_) for _ in input().split(' ')]
print(solve(hs))


import collections
count = int(input().strip())
heights = [int(i) for i in input().strip().split(' ')]
stack = collections.deque([])
max_area = -1
i = 0
while i < count:
	height = heights[i]
	if len(stack) == 0 or height >= heights[stack[-1]]:
		stack.append(i)
		i += 1
	else:
		top = stack.pop()
		area = heights[top] * (i if len(stack) == 0 else i - stack[-1] - 1)
		max_area = max(max_area, area)
while len(stack) > 0:
	top = stack.pop()
	area = heights[top] * (i if len(stack) == 0 else i - stack[-1] - 1)
	max_area = max(max_area, area)
print(max_area)


n = int(input())
h = [int(v) for v in input().split()]
m = []
top = 0
s = 0
for i in range(n):
	if h[i] > top:
		top = h[i]
		m.append((top, i))
	elif h[i] < top:
		top = h[i]
		lm = len(m)
		lx = 0
		while lm > 0 and m[lm - 1][0] > top:
			(lh, lx) = m.pop()
			s = max(s, lh * (i - lx))
			lm -= 1
		m.append((top, lx))
while m:
	(lh, lx) = m.pop()
	s = max(s, lh * (i - lx + 1))
print(s)


n = int(input().strip())
buildings = [int(x) for x in input().strip().split()]

def find_min_pos(l):
	i_min = 0
	x_min = None
	for (i, x) in enumerate(l):
		if x_min is None or x < x_min:
			x_min = x
			i_min = i
	return i_min

def solve(building):
	if len(building) == 0:
		return 0
	i = find_min_pos(building)
	return max(max(len(building) * building[i], solve(building[:i])), solve(building[i + 1:]))
print(solve(buildings))


class Node:

	def __init__(self, data, min):
		self.data = data
		self.min = min

class Stack:

	def __init__(self):
		self.stack = []

	def push(self, data):
		self.stack.append(data)

	def empty(self):
		if len(self.stack) is 0:
			return 1
		return 0

	def pop(self):
		return self.stack.pop()

	def peek(self):
		return self.stack[len(self.stack) - 1]
nqry = int(input())
max_area = 0
top_area = 0
s = Stack()
qry = input().strip().split(' ')
i = 0
while i < nqry:
	if s.empty() or int(qry[s.peek()]) <= int(qry[i]):
		s.push(i)
		i += 1
	else:
		top = s.pop()
		top_area = int(qry[top]) * (i if s.empty() else i - s.peek() - 1)
		if max_area < top_area:
			max_area = top_area
while s.empty() == 0:
	top = s.pop()
	top_area = int(qry[top]) * (i if s.empty() else i - s.peek() - 1)
	if max_area < top_area:
		max_area = top_area
print(max_area)


n = int(input())
heights = list(map(int, input().split()))
stack = []
max_area = 0
area = 0
i = 0
while i < n:
	if not stack or heights[stack[-1]] <= heights[i]:
		stack.append(i)
		i += 1
	else:
		top = stack.pop()
		if not stack:
			area = heights[top] * i
		else:
			area = heights[top] * (i - stack[-1] - 1)
		if area > max_area:
			max_area = area
while stack:
	top = stack.pop()
	if not stack:
		area = heights[top] * i
	else:
		area = heights[top] * (i - stack[-1] - 1)
	if area > max_area:
		max_area = area
print(max_area)


maxStack = []

def maxCalc(numList):
	if len(numList) > 0:
		if len(maxStack) == 0 or maxStack[-1] < len(numList) * min(numList):
			maxStack.append(len(numList) * min(numList))
		else:
			maxStack.append(maxStack[-1])
	if len(numList) > 1:
		minVal = min(numList)
		valLen = len(numList)
		positions = [i for (i, j) in enumerate(numList) if j == minVal]
		prevVal = 0
		for i in range(0, len(positions)):
			if i == 0:
				maxCalc(numList[0:positions[i]])
			if i + 1 < len(positions):
				maxCalc(numList[positions[i] + 1:positions[i + 1]])
			else:
				maxCalc(numList[positions[i] + 1:len(numList)])
numIns = int(input().strip())
numbers = list(map(int, input().strip().split(' ')))
maxCalc(numbers)
print(maxStack[-1])


def sum_to_left(h, i, buildings):
	res = 0
	while i > 0 and buildings[i - 1] >= h:
		res += h
		i -= 1
	return res

def sum_to_right(h, i, n, buildings):
	res = 0
	while i < n - 1 and buildings[i + 1] >= h:
		res += h
		i += 1
	return res
n = int(input().strip())
buildings = [int(x) for x in input().strip().split(' ')]
max_area = 0
for (i, height) in enumerate(buildings):
	area = sum_to_left(height, i, buildings) + height + sum_to_right(height, i, n, buildings)
	if area > max_area:
		max_area = area
print(max_area)


n = int(input().strip())
heights = [int(x) for x in input().strip().split()]
stack = list()
m = 0
i = 0
while i < n:
	h = heights[i]
	if not len(stack) or h >= stack[-1][1]:
		stack.append((i, h))
		i += 1
	else:
		(i_p, h_p) = stack.pop()
		m = max(h_p * (i - stack[-1][0] - 1 if len(stack) else i), m)
while len(stack):
	(i_p, h_p) = stack.pop()
	m = max(h_p * (i - stack[-1][0] - 1 if len(stack) else i), m)
print(m)


import sys
f = sys.stdin
N = int(f.readline())
height_list = [int(h) for h in f.readline().split(' ')]
max_area = 0
for i in range(N):
	h = height_list[i]
	area = h
	for j in range(i + 1, N):
		if height_list[j] >= h:
			area += h
		else:
			break
	for j in range(i - 1, -1, -1):
		if height_list[j] >= h:
			area += h
		else:
			break
	max_area = max(max_area, area)
print(max_area)