You are given a list of $N$ numbers $a_1,a_2,\ldots,a_n$. For each element at position $\boldsymbol{i}$ ($1\leq i\leq N$), we define $\text{Left}(i)$ and $\textit{Right}(i)$ as: 

$\text{Left}(i)$ = closest index j such that j < i and $a_j>a_i$. If no such j exists then $\text{Left}(i)$ = 0. 

$\textit{Right}(i)$ = closest index k such that k > i and $a_k>a_i$. If no such k exists then $\textit{Right}(i)$ = 0.   

We define $\textit{IndexProduct(i)}$ = $\text{Left}(i)$ * $\textit{Right}(i)$. You need to find out the maximum $\textit{IndexProduct(i)}$ among all i.

Input Format

The first line contains an integer $N$, the number of integers.
The next line contains the $N$ integers describing the list a[1..N].

Constraints 

$1\leq N\leq10^5$ 

$1\leq a_i\leq10^9$

Output Format

Output the maximum $\textit{IndexProduct}$ among all indices from $1$ to $N$. 

Sample Input
5
5 4 3 4 5

Sample Output
8

Explanation

We can compute the following:

$IndexProduct(1)=0$ 

$IndexProduct(2)=1\times5=5$ 

$IndexProduct(3)=2\times4=8$ 

$IndexProduct(4)=1\times5=5$ 

$IndexProduct(5)=0$

The largest of these is 8, so it is the answer.

Source: hackerrank | Difficulty: MEDIUM
Tags: Data structures


Solutions:
def lefts(L):
	left = []
	maxes = []
	for i in range(len(L)):
		while maxes and L[maxes[-1]] <= L[i]:
			maxes.pop()
		if not maxes:
			left.append(-1)
		else:
			left.append(maxes[-1])
		maxes.append(i)
	return left

def rights(L):
	right = []
	maxes = []
	for i in range(len(L) - 1, -1, -1):
		while maxes and L[maxes[-1]] <= L[i]:
			maxes.pop()
		if not maxes:
			right.append(-1)
		else:
			right.append(maxes[-1])
		maxes.append(i)
	right.reverse()
	return right

def indexProduct(L):
	left = lefts(L)
	right = rights(L)
	products = ((left[i] + 1) * (right[i] + 1) for i in range(len(L)))
	return max(products)
input()
L = [int(n) for n in input().split()]
print(indexProduct(L))


N = int(input())
a = list(map(int, input().split()))
L = [0 for i in range(N)]
R = [0 for i in range(N)]
stack = []
for i in range(N):
	while len(stack) > 0 and a[stack[-1]] < a[i]:
		R[stack.pop()] = i + 1
	stack.append(i)
stack = []
for i in range(N):
	while len(stack) > 0 and a[stack[-1]] < a[N - 1 - i]:
		L[stack.pop()] = N - i
	stack.append(N - 1 - i)
ans = 0
for i in range(N):
	ans = max(ans, L[i] * R[i])
print(ans)


def get_maxright(a, i, start):
	while start < len(a):
		if a[start] > a[i]:
			return start
		start += 1
	return -1

def get_maxleft(a, i, start):
	while start >= 0:
		if a[start] > a[i]:
			return start
		start -= 1
	return -1
n = int(input())
a = [int(x) for x in input().split()]
maxleft = 0
maxright = 0
maxip = 0
for i in range(1, len(a) - 1):
	if a[i - 1] > a[i]:
		maxleft = i - 1
		maxright = get_maxright(a, i, i + 1)
	elif a[i] > a[i - 1]:
		maxleft = get_maxleft(a, i, maxleft)
		maxright = get_maxright(a, i, maxright)
	if maxleft != -1 and maxright != -1:
		newmaxip = (maxleft + 1) * (maxright + 1)
		if newmaxip > maxip:
			maxip = newmaxip
print(maxip)


from collections import deque
n = int(input())
data = [int(x) for x in input().split()]
left = [0 for i in range(n)]
right = left[:]
stack = deque()
for i in range(n):
	if len(stack) == 0:
		stack.append((data[i], i))
	else:
		while len(stack) and stack[-1][0] < data[i]:
			right[stack[-1][1]] = i + 1
			stack.pop()
		else:
			stack.append((data[i], i))
stack.clear()
for i in range(n - 1, -1, -1):
	if len(stack) == 0:
		stack.append((data[i], i))
	else:
		while len(stack) and stack[-1][0] < data[i]:
			left[stack[-1][1]] = i + 1
			stack.pop()
		else:
			stack.append((data[i], i))
res = 0
for i in range(n):
	res = max(res, left[i] * right[i])
print(res)


def right(numbers, i, right_i):
	max_index = len(numbers) - 1
	val = numbers[i]
	i += 1
	while i <= max_index and i > 0:
		if numbers[i] > val:
			return i
		else:
			i = right_i[max_index - i]
	return -1

def left(numbers, i, left_i):
	val = numbers[i]
	i -= 1
	while i >= 0:
		if numbers[i] > val:
			return i
		else:
			i = left_i[i]
	return -1
N = int(input())
numbers = [int(num) for num in input().split()]
product = 0
max_product = 0
left_i = []
right_i = []
index = 0
max_index = len(numbers) - 1
while index <= max_index:
	left_i.append(left(numbers, index, left_i))
	index += 1
index = max_index
while index >= 0:
	right_i.append(right(numbers, index, right_i))
	index -= 1
for (index, num) in enumerate(numbers):
	product = (left_i[index] + 1) * (right_i[max_index - index] + 1)
	if product > max_product:
		max_product = product
print(max_product)


N = int(input())
A = list(map(int, input().split()))
L = [0] * N
l = []
for i in range(N):
	while l and l[-1][0] <= A[i]:
		l.pop()
	if l:
		L[i] = l[-1][1]
	l.append((A[i], i + 1))
R = [0] * N
r = []
for i in range(N - 1, -1, -1):
	while r and r[-1][0] <= A[i]:
		r.pop()
	if r:
		R[i] = r[-1][1]
	r.append((A[i], i + 1))
print(max([l * r for (l, r) in zip(L, R)]))


def log(text):
	pass

def get_max_indexproduct(numbers):
	max_indexproduct = 0
	left = [None] * len(numbers)
	right = [None] * len(numbers)
	if len(numbers) < 3:
		return 0
	else:
		max_indexproduct = find_max_indexproduct(numbers, 0, len(numbers), left, right)
	return max_indexproduct

def find_max_indexproduct(numbers, start, end, left, right):
	if start == end:
		return 0
	i = int((start + end) / 2)
	log('i: %d, start: %s, end: %d' % (i, start, end))
	li = i - 1
	while li >= 0:
		log('li: %d' % li)
		if numbers[i] < numbers[li]:
			log('left[%d] = %d' % (i, li))
			left[i] = li
			break
		elif not left[li] == None:
			li = left[li]
		else:
			li -= 1
	if left[i] == None:
		log('left[%d] = -1' % i)
		left[i] = -1
	ri = i + 1
	while ri < len(numbers):
		log('ri: %d' % ri)
		if numbers[i] < numbers[ri]:
			log('right[%d] = %d' % (i, ri))
			right[i] = ri
			break
		elif not right[ri] == None:
			ri = right[ri]
		else:
			ri += 1
	if right[i] == None:
		log('right[%d] = -1' % i)
		right[i] = len(numbers)
	if left[i] >= 0 and right[i] < len(numbers):
		indexproduct = (left[i] + 1) * (right[i] + 1)
		return max(indexproduct, find_max_indexproduct(numbers, start, i, left, right), find_max_indexproduct(numbers, i + 1, end, left, right))
	else:
		return max(find_max_indexproduct(numbers, start, i, left, right), find_max_indexproduct(numbers, i + 1, end, left, right))
length = int(input())
numbers = [int(s) for s in input().strip().split(' ')]
print(get_max_indexproduct(numbers))


n = int(input())
a = [int(i) for i in input().split()]
left = [-1] * n
right = [-1] * n
s = [0]
for i in range(1, n):
	while len(s) > 0 and a[s[-1]] <= a[i]:
		s.pop()
	left[i] = s[-1] if len(s) > 0 else -1
	s.append(i)
s = [n - 1]
for i in reversed(range(n - 1)):
	while len(s) > 0 and a[s[-1]] <= a[i]:
		s.pop()
	right[i] = s[-1] if len(s) > 0 else -1
	s.append(i)
max_prod = 0
for i in range(n):
	max_prod = max(max_prod, (left[i] + 1) * (right[i] + 1))
print(max_prod)


from heapq import heappush, heappop

def GetIndex(N, A, is_reverse):
	index = [0 for i in range(N)]
	min_heap = []
	for i in range(N):
		if is_reverse:
			i = N - i - 1
		while len(min_heap) > 0 and min_heap[0][0] < A[i]:
			element = heappop(min_heap)
			index[element[1]] = i + 1
		heappush(min_heap, (A[i], i))
	return index

def IndexProduct(N, A):
	right_index = GetIndex(N, A, False)
	left_index = GetIndex(N, A, True)
	max_index_product = 0
	for i in range(N):
		index_product = right_index[i] * left_index[i]
		if max_index_product < index_product:
			max_index_product = index_product
	return max_index_product

def main():
	N = int(input())
	A = input().split()
	for i in range(N):
		A[i] = int(A[i])
	print(IndexProduct(N, A))
main()


def solve(array, n):
	left = [-1] * n
	largest_left = array[0]
	for i in range(1, n):
		if array[i] >= largest_left:
			largest_left = array[i]
			continue
		if array[i - 1] > array[i]:
			left[i] = i - 1
		else:
			idx = left[i - 1]
			while idx >= 0:
				if array[idx] > array[i]:
					left[i] = idx
					break
				idx -= 1
	right = [-1] * n
	largest_right = array[n - 1]
	for i in range(n - 2, -1, -1):
		if array[i] >= largest_right:
			largest_right = array[i]
			continue
		if array[i + 1] > array[i]:
			right[i] = i + 1
		else:
			idx = right[i + 1]
			while idx < n:
				if array[idx] > array[i]:
					right[i] = idx
					break
				idx += 1
	max_product = 0
	for i in range(n):
		max_product = max((left[i] + 1) * (right[i] + 1), max_product)
	return max_product
n = int(input())
array = [int(x) for x in input().split()]
print(solve(array, n))


def find_max_indexproduct(list_num, n):
	left_i = [0] * n
	right_i = [0] * n
	for i in range(1, n):
		if list_num[i] < list_num[i - 1]:
			left_i[i] = i
		if list_num[i] == list_num[i - 1]:
			left_i[i] = left_i[i - 1]
		if list_num[i] > list_num[i - 1]:
			for j in range(left_i[i - 1], -1, -1):
				if list_num[j] > list_num[i]:
					left_i[i] = j + 1
					break
	for i in range(n - 1, 0, -1):
		if list_num[i] > list_num[i - 1]:
			right_i[i - 1] = i + 1
		if list_num[i] == list_num[i - 1]:
			right_i[i - 1] = right_i[i]
		if list_num[i] < list_num[i - 1]:
			for j in range(right_i[i], n):
				if list_num[j] > list_num[i - 1]:
					right_i[i - 1] = j + 1
					break
	print(max([left_i[i] * right_i[i] for i in range(n)]))
n = int(input())
list_num = [int(x) for x in input().split()]
find_max_indexproduct(list_num, n)


def left(ar, n, m):
	x = ar[n]
	i = n - 1
	c = len(ar)
	while i >= 0:
		if ar[i] > x:
			break
		i -= 1
		if i * c < m:
			i = -1
	if i < 0:
		return 0
	else:
		return i + 1

def right(ar, n):
	x = ar[n]
	i = n + 1
	c = len(ar)
	while i < c:
		if ar[i] > x:
			break
		i += 1
	if i == c:
		return 0
	else:
		return i + 1
n = int(input())
ar = input().split()
ar = [int(num) for num in ar]
ml = [0] * n
mr = [0] * n
m = ar[0]
ml[0] = ar[0]
k = mr[n - 1] = ar[n - 1]
for i in range(n):
	if ar[i] > m:
		m = ar[i]
	ml[i] = m
	x = n - i - 1
	if ar[x] > k:
		k = ar[x]
	mr[x] = k
max = 0
for i in range(n - 2, 0, -1):
	if ar[i] >= ml[i] or ar[i] >= mr[i]:
		continue
	if i * n < max:
		break
	l = left(ar, i, max)
	if l * n < max:
		continue
	r = right(ar, i)
	y = l * r
	if y > max:
		max = y
print(max)


def getLeft(lis):
	res = []
	stack = [(10 ** 9 + 1, 0)]
	for (i, x) in enumerate(lis):
		while stack[-1][0] <= x:
			stack.pop()
		res.append(stack[-1][1])
		stack.append((x, i + 1))
	return res

def getRight(lis):
	res = []
	stack = [(10 ** 9 + 1, 0)]
	for (i, x) in reversed(list(enumerate(lis))):
		while stack[-1][0] <= x:
			stack.pop()
		res.insert(0, stack[-1][1])
		stack.append((x, i + 1))
	return res
n = int(input())
lis = list(map(int, input().split()))
left = getLeft(lis)
right = getRight(lis)
m = 0
for (x, y) in zip(left, right):
	m = max(m, x * y)
print(m)


n = int(input().strip())
ar = [None] + [int(i) for i in input().strip().split()]
maxpi = 0
st = len(ar)
for i in range(2, len(ar)):
	if ar[i] < ar[i - 1]:
		st = i
		break
ed = 1
for i in range(len(ar) - 1, st - 1, -1):
	if ar[i - 1] > ar[i]:
		ed = i + 1
		break
lt = None
lri = None
lli = None
for i in range(st, ed):
	t = ar[i]
	li = 0
	ri = 0
	if lli != 0 or t < lt:
		for j in range(i + 1, min(ed + 1, len(ar))):
			if ar[j] > t:
				li = j
				break
	else:
		li = 0
	lli = li
	if li > 0:
		if lri != 0 or t < lt:
			for j in range(i - 1, st - 2, -1):
				if ar[j] > t:
					ri = j
					break
		else:
			ri = 0
	pi = li * ri
	lri = ri
	lt = t
	if pi > maxpi:
		maxpi = pi
print(maxpi)


def max_index_product(seq):
	n = len(seq)
	maxproduct = 0
	if n == 0:
		return maxproduct
	stack = []
	fromlow = []
	for (i, e) in enumerate(seq):
		while stack and e >= stack[-1][0]:
			stack.pop()
		ind = stack[-1][1] + 1 if stack else 0
		fromlow.append(ind)
		stack.append((e, i))
	stack = []
	fromhigh = []
	for (i, e) in reversed(list(enumerate(seq))):
		while stack and e >= stack[-1][0]:
			stack.pop()
		ind = stack[-1][1] + 1 if stack else 0
		fromhigh.append(ind)
		stack.append((e, i))
	fromhigh = fromhigh[::-1]
	return max((l * h for (l, h) in zip(fromlow, fromhigh)))
T = int(input())
seq = list(map(int, input().split()))[:T]
print(max_index_product(seq))


sizeOfArr = int(input())
A = [int(n) for n in input().split()]

def left(i):
	val = A[i]
	for j in range(i)[::-1]:
		if A[j] > val:
			return j
	return 0

def right(i):
	val = A[i]
	for j in range(i + 1, len(A)):
		if A[j] > val:
			return j
	return 0

def indexProduct(i):
	return (left(i) + 1) * (right(i) + 1)

def findPeak():
	for i in range(1, len(A))[::-1]:
		if A[i - 1] < A[i]:
			return i
	return 0

def findTrough():
	for i in range(1, findPeak())[::-1]:
		if A[i - 1] > A[i]:
			return i
	return 0

def calcLeftArr():
	trough = findTrough()
	leftArr = sorted(enumerate(A[:trough]), key=lambda p: -p[1])
	i = 1
	while i < len(leftArr):
		if leftArr[i][0] < leftArr[i - 1][0]:
			del leftArr[i]
		else:
			i += 1
	return leftArr
maxIndexProduct = 0
trough = findTrough()
peak = findPeak()
if len(A) > 2 and trough != 0 and (peak != 0):
	leftArr = calcLeftArr()
	rightBoundary = peak - 1
	while A[rightBoundary] >= leftArr[0][1]:
		rightBoundary -= 1
	for i in range(trough, rightBoundary + 1)[::-1]:
		while len(leftArr) > 1 and (not (leftArr[0][1] > A[i] and leftArr[1][1] <= A[i])):
			del leftArr[0]
		foundLeft = leftArr[0][0]
		maxIndexProduct = max(maxIndexProduct, (foundLeft + 1) * (i + 2))
print(maxIndexProduct)


def max_index_product(N, A):
	L = [0 for _ in range(N)]
	R = [0 for _ in range(N)]
	for i in range(1, N):
		pos1 = i - 1
		while pos1 >= 0:
			if A[pos1] > A[i]:
				L[i] = pos1 + 1
				break
			pos1 = L[pos1] - 1
	for i in range(N - 2, -1, -1):
		pos2 = i + 1
		while pos2 >= 0:
			if A[pos2] > A[i]:
				R[i] = pos2 + 1
				break
			pos2 = R[pos2] - 1
	return max((x * y for (x, y) in zip(L, R)))

def main():
	N = int(input())
	A = [int(i) for i in input().split()]
	print(max_index_product(N, A))
main()


first = []
second = []

def s_empty(stack):
	return len(stack) == 0

def s_top(stack):
	return stack[len(stack) - 1]
a = int(input())
arr = list(map(lambda x: int(x), input().split()))
arr.insert(0, None)
leftprod = list(map(lambda x: 0, arr))
rightprod = list(map(lambda x: 0, arr))
g = 1
while g <= a:
	while not s_empty(first) and s_top(first)[0] <= arr[g]:
		first.pop()
	if s_empty(first):
		first.append((arr[g], g))
		g += 1
		continue
	leftprod[g] = s_top(first)[1]
	first.append((arr[g], g))
	g += 1
g = a
while g >= 1:
	while not s_empty(second) and s_top(second)[0] <= arr[g]:
		second.pop()
	if s_empty(second):
		second.append((arr[g], g))
		g -= 1
		continue
	rightprod[g] = s_top(second)[1]
	second.append((arr[g], g))
	g -= 1
ans = 0
g = 1
while g <= a:
	t = leftprod[g] * rightprod[g]
	if t > ans:
		ans = t
	g += 1
print(ans)


def get_left(arr, i, left):
	j = i - 1
	while arr[j] <= arr[i] and j > 0:
		j = left[j] - 1
	if arr[j] <= arr[i]:
		return 0
	return j + 1

def get_right(arr, i, right):
	j = i + 1
	while arr[j] <= arr[i] and j < len(arr) and (j > 0):
		j = right[j] - 1
	if arr[j] <= arr[i]:
		return 0
	return j + 1
n = int(input())
arr = [int(x) for x in input().split()]
left = [0 for x in range(len(arr))]
hl = arr[0]
for i in range(1, len(arr)):
	if arr[i] < hl:
		left[i] = get_left(arr, i, left)
	else:
		hl = arr[i]
right = [0 for x in range(len(arr))]
hr = arr[len(arr) - 1]
for i in range(len(arr) - 2, -1, -1):
	if arr[i] < hr:
		right[i] = get_right(arr, i, right)
	else:
		hr = arr[i]
best = 0
for i in range(len(arr)):
	p = left[i] * right[i]
	if p > best:
		best = p
print(best)


def INDEXPRODUCT(l):
	L = [-1 for _ in l]
	R = [-1 for _ in l]
	for i in range(1, len(l)):
		idx = i - 1
		while idx != -1:
			if l[idx] > l[i]:
				L[i] = idx
				break
			idx = L[idx]
	for i in range(len(l) - 2, -1, -1):
		idx = i + 1
		while idx != -1:
			if l[idx] > l[i]:
				R[i] = idx
				break
			idx = R[idx]
	max_product = 0
	for i in range(len(l)):
		tmp = (L[i] + 1) * (R[i] + 1)
		if max_product < tmp:
			max_product = tmp
	return max_product
N = input()
l = [int(i) for i in input().strip().split()]
print(INDEXPRODUCT(l))


from fileinput import input
import sys

def find():
	lines = input()
	n = [int(x) for x in lines[0].strip().split()][0]
	a = [int(x) for x in lines[1].strip().split()]
	root = ST(a, 0, n - 1)
	maxprod = 0
	for i in range(n):
		rv = rightquery(root, a, i)
		if rv == sys.maxsize:
			rv = 0
		else:
			rv += 1
		lv = leftquery(root, a, i)
		if lv == -1:
			lv = 0
		else:
			lv += 1
		maxprod = max(maxprod, rv * lv)
	print(maxprod, end='\n')

class ST:

	def __init__(self, a, left, right):
		self.key = [left, right]
		self.val = [-sys.maxsize - 1, sys.maxsize]
		self.left = None
		self.right = None
		self.build(a, left, right)

	def build(self, a, left, right):
		if left == right:
			self.val = [a[left], a[right]]
			return
		mid = (left + right) // 2
		self.left = ST(a, left, mid)
		self.right = ST(a, mid + 1, right)
		lv = self.left.val
		rv = self.right.val
		self.val = [min(lv[0], rv[0]), max(lv[1], rv[1])]

def rightquery(root, a, k):
	res = sys.maxsize
	if root == None:
		return res
	(left, right) = root.key
	if right <= k:
		return res
	elif left > k:
		if left == right and a[left] > a[k]:
			return left
		if root.val[1] <= a[k]:
			return res
		elif root.left.val[1] > a[k]:
			return rightquery(root.left, a, k)
		else:
			return rightquery(root.right, a, k)
	else:
		return min(rightquery(root.left, a, k), rightquery(root.right, a, k))

def leftquery(root, a, k):
	res = -1
	if root == None:
		return res
	(left, right) = root.key
	if left >= k:
		return res
	elif right < k:
		if left == right and a[right] > a[k]:
			return right
		if root.val[1] <= a[k]:
			return res
		elif root.right.val[1] > a[k]:
			return leftquery(root.right, a, k)
		else:
			return leftquery(root.left, a, k)
	else:
		return max(leftquery(root.left, a, k), leftquery(root.right, a, k))
find()


def le_entrada():
	N = int(input())
	vetor_inteiros = str(input()).split()
	return [int(v) for v in vetor_inteiros]

def produto_maximo(vetor_inteiros):
	produto_maximo = -1
	vetor_left = resolve_left(vetor_inteiros)
	vetor_right = resolve_right(vetor_inteiros)
	for i in range(len(vetor_inteiros)):
		left = vetor_left[i] + 1
		right = vetor_right[i] + 1
		produto_maximo = max(produto_maximo, left * right)
	return produto_maximo

def resolve_left(vetor_inteiros):
	L = [-1 for _ in vetor_inteiros]
	for i in range(1, len(vetor_inteiros)):
		index = i - 1
		while index != -1:
			if vetor_inteiros[index] > vetor_inteiros[i]:
				L[i] = index
				break
			index = L[index]
	return L

def resolve_right(vetor_inteiros):
	R = [-1 for _ in vetor_inteiros]
	for i in range(len(vetor_inteiros) - 2, -1, -1):
		index = i + 1
		while index != -1:
			if vetor_inteiros[index] > vetor_inteiros[i]:
				R[i] = index
				break
			index = R[index]
	return R
print(produto_maximo(le_entrada()))


def le_entrada():
	input()
	return [int(v) for v in str(input()).split()]

def max_produto(valores, u_left, u_right):
	mp = 0
	for i in range(len(valores)):
		le = left(valores, i, u_left)
		if le > -1:
			ri = right(valores, i, u_right)
			if ri > -1:
				mp = max(mp, (le + 1) * (ri + 1))
	return mp

def left(valores, idx_val, u_left):
	res = -1
	idx_u = valores[idx_val][1]
	while idx_u > -1 and valores[u_left[idx_u]][0] <= valores[idx_val][0]:
		idx_u -= 1
	if idx_u > -1:
		res = u_left[idx_u]
	return res

def right(valores, idx_val, u_right):
	res = -1
	idx_u = valores[idx_val][2]
	while idx_u < len(u_right) and valores[u_right[idx_u]][0] <= valores[idx_val][0]:
		idx_u += 1
	if idx_u > -1 and idx_u < len(u_right):
		res = u_right[idx_u]
	return res

def limites(valores):
	resp = []
	u_left = []
	u_right = []
	for i in range(len(valores)):
		if i < len(valores) - 1 and valores[i + 1] < valores[i]:
			u_left.append(i)
		if i > 0 and valores[i - 1] < valores[i]:
			u_right.append(i)
	iml = 0
	imr = 0
	for i in range(len(valores)):
		resp.append([valores[i], -1, -1])
		if len(u_left) > 0 and len(u_right) > 0:
			while iml < len(u_left) and u_left[iml] < i:
				iml += 1
			while imr < len(u_right) and u_right[imr] <= i:
				imr += 1
			if iml > 0 and u_left[iml - 1] < i:
				resp[len(resp) - 1][1] = iml - 1
			if imr < len(u_right) and u_right[imr] > i:
				resp[len(resp) - 1][2] = imr
	return (resp, u_left, u_right)
valores = le_entrada()
(valores, u_left, u_right) = limites(valores)
print(max_produto(valores, u_left, u_right))


import sys

def find_inflexion_point(values):
	if len(values) < 3:
		raise RuntimeError("Didn't find inflexion point")
	for i in range(len(values) - 2, 0, -1):
		if values[i - 1] > values[i] < values[i + 1]:
			return i
	raise RuntimeError("Didn't find inflexion point")

def find_product_index(values, index):
	l_index = index - 1
	left = values[l_index]
	for r_index in range(l_index + 2, len(values)):
		if values[r_index] >= left:
			return (r_index + 1) * (l_index + 1)
	return len(values) * (l_index + 1)
input()
values = list(map(int, input().split()))
try:
	node_index = find_inflexion_point(values)
except RuntimeError:
	print(0)
	sys.exit(0)
product = find_product_index(values, node_index)
print(product)


numbers_count = int(input())
numbers = []
numbers = input().split(' ')
numbers = list(map(int, numbers))
max_index_product = 0
stack = []
left_indexes = {}
right_indexes = {}
for i in range(numbers_count):
	current_number = {'index': i, 'value': numbers[i]}
	while stack and stack[-1]['value'] <= numbers[i]:
		stack.pop()
	if not stack:
		stack.append(current_number)
		left_indexes[i] = -1
		continue
	left_indexes[i] = stack[-1]['index']
	stack.append(current_number)
stack = []
for j in range(numbers_count - 1, -1, -1):
	current_number = {'index': j, 'value': numbers[j]}
	while stack and stack[-1]['value'] <= numbers[j]:
		stack.pop()
	if not stack:
		stack.append(current_number)
		right_indexes[j] = -1
		continue
	right_indexes[j] = stack[-1]['index']
	stack.append(current_number)
for k in range(numbers_count):
	index_product = (left_indexes[k] + 1) * (right_indexes[k] + 1)
	if index_product > max_index_product:
		max_index_product = index_product
print(max_index_product)


N = int(input())
A = [int(x) for x in input().split()]
(lefts, rights) = ([0] * len(A), [0] * len(A))
stack = []
for i in range(len(A)):
	while stack and A[stack[-1]] <= A[i]:
		stack.pop()
	lefts[i] = stack[-1] if stack else -1
	stack.append(i)
stack = []
for i in range(len(A) - 1, -1, -1):
	while stack and A[stack[-1]] <= A[i]:
		stack.pop()
	rights[i] = stack[-1] if stack else -1
	stack.append(i)
maxprod = 0
for i in range(len(A)):
	maxprod = max(maxprod, (lefts[i] + 1) * (rights[i] + 1))
print(maxprod)


N = int(input())
a = list(map(int, input().split()))
left = [0] * N
stack = []
for (index, value) in enumerate(a):
	while stack and value >= stack[-1][0]:
		stack.pop()
	if stack:
		left[index] = stack[-1][1]
	stack.append((value, index + 1))
stack.clear()
right = [0] * N
for (index, value) in enumerate(a[::-1]):
	while stack and value >= stack[-1][0]:
		stack.pop()
	if stack:
		right[N - 1 - index] = stack[-1][1]
	stack.append((value, N - index))
res = 0
for (l, r) in zip(left, right):
	res = max(res, l * r)
print(res)


def fun(a, n):
	left = [0 for i in range(n)]
	right = [0 for i in range(n)]
	for i in range(1, n):
		if a[i - 1] > a[i]:
			left[i] = i
		else:
			prev = left[i - 1]
			while a[prev - 1] <= a[i] and left[prev - 1] > 0:
				prev = left[prev - 1]
			if a[prev - 1] > a[i]:
				left[i] = prev
	for i in range(n - 2, -1, -1):
		if a[i + 1] > a[i]:
			right[i] = i + 2
		else:
			prev = right[i + 1]
			while a[prev - 1] <= a[i] and right[prev - 1] > 0:
				prev = right[prev - 1]
			if a[prev - 1] > a[i]:
				right[i] = prev
	ans = 0
	for i in range(n):
		if ans < left[i] * right[i]:
			ans = left[i] * right[i]
	print(ans)
n = int(input())
l = [int(i) for i in input().split()]
fun(l, n)


from sys import stderr

def main():
	n = int(input())
	a = [int(fld) for fld in input().strip().split()]
	print(maxindexproduct(a))

def maxindexproduct(a):
	left = leftindex(sorted(((elt, i) for (i, elt) in enumerate(a))))
	right = leftindex(sorted(((elt, i) for (i, elt) in enumerate(reversed(a)))))
	right = [len(a) - r if r != -1 else 0 for r in reversed(right)]
	return max(((L + 1) * R for (L, R) in zip(left, right)))

def leftindex(invidx):
	nextidx = list(range(len(invidx)))
	ret = [None] * len(invidx)
	for (elt, ind) in invidx:
		p = ind - 1
		trans = []
		while p != -1 and nextidx[p] != p:
			trans.append(p)
			p = nextidx[p]
		for oldp in trans:
			nextidx[oldp] = p
		ret[ind] = p
		nextidx[ind] = p
	print(ret, file=stderr)
	return ret
main()


n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)


n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)


import sys
from copy import deepcopy

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	arr = [0] + arr + [0]
	max_value = 0
	left = find_left(arr)
	reverse_arr = list(reversed(arr))
	right = find_left(reverse_arr)
	right = ['$'] + list(reversed(right[1:]))
	for i in range(1, len(arr) - 2):
		if right[i] != 0:
			right[i] = len(arr) - 1 - right[i]
	for i in range(1, n + 1):
		value = left[i] * right[i]
		if value > max_value:
			max_value = value
	print(max_value)

def find_left(arr):
	stack = [0]
	left = ['$']
	i = 1
	while i < len(arr) - 1:
		if arr[stack[-1]] > arr[i]:
			left.append(stack[-1])
			stack.append(i)
		else:
			while len(stack) > 1 and arr[stack[-1]] <= arr[i]:
				stack.pop(-1)
			left.append(stack[-1])
			stack.append(i)
		if len(stack) == 1 and i == 1:
			left.append(stack[-1])
			stack.append(i)
		i += 1
	return left
main()


n = int(input())
a = [int(i) for i in input().split()]
stack = []
prod = 0
for (i, num) in enumerate(reversed(a)):
	if not stack:
		stack.append((num, n - i))
	else:
		(last, j) = stack[-1]
		if num <= last:
			stack.append((num, n - i))
		else:
			while last < num:
				stack.pop()
				if not stack:
					break
				(last, j) = stack[-1]
			if stack:
				prod = max(prod, (n - i) * j)
			stack.append((num, n - i))
print(prod)


arr_len = int(input())
arr = list(map(int, input().strip().split(' ')))[:arr_len]

def get_closest_bigger_id(arr, start, stop, steps):
	bigger_ids = []
	stack = []
	for i in range(start, stop, steps):
		while len(stack) > 0 and arr[stack[-1]] <= arr[i]:
			stack.pop()
		if len(stack) == 0:
			bigger_ids.append(-1)
		else:
			bigger_ids.append(stack[-1])
		stack.append(i)
	return bigger_ids
left = get_closest_bigger_id(arr, 0, arr_len, 1)
right = get_closest_bigger_id(arr, arr_len - 1, -1, -1)
right.reverse()
max_index_prod = -1
for i in range(arr_len):
	ip = (left[i] + 1) * (right[i] + 1)
	if ip > max_index_prod:
		max_index_prod = ip
print(max_index_prod)


n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)


N = int(input())
A = [int(x) for x in input().split()]
left = [-1] * N
for i in range(1, N):
	now = i - 1
	while now != -1 and A[now] <= A[i]:
		now = left[now]
	left[i] = now
right = [-1] * N
for i in reversed(range(N - 1)):
	now = i + 1
	while now != -1 and A[now] <= A[i]:
		now = right[now]
	right[i] = now
print(max(((l + 1) * (r + 1) for (l, r) in zip(left, right))))


n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)


n = int(input())
arr = [int(x) for x in input().split()]
stack = []
left_indices = []
right_indices = []
for (i, val) in enumerate(arr, 1):
	while stack and stack[-1][0] <= val:
		stack.pop()
	left_indices.append(stack[-1][1] if stack else 0)
	stack.append((val, i))
stack = []
for (i, val) in enumerate(arr[::-1]):
	while stack and stack[-1][0] <= val:
		stack.pop()
	right_indices.append(stack[-1][1] if stack else 0)
	stack.append((val, n - i))
print(max((x * y for (x, y) in zip(left_indices, right_indices[::-1]))))


n = int(input())
arr = list(map(int, input().split()))
rights = []
lefts = []
for i in range(n - 1):
	if arr[i] > arr[i + 1]:
		lefts.append(i)
	elif arr[i] < arr[i + 1]:
		rights.append(i + 1)
right = 0
left = 0
while rights and lefts:
	if rights[-1] <= lefts[-1]:
		lefts = lefts[:-1]
	else:
		left = lefts[-1] + 1
		break
if lefts:
	while rights:
		if rights[-1] > lefts[-1]:
			right = rights[-1] + 1
			rights = rights[:-1]
		else:
			break
print(right * left)


def closest_max(a, n):
	max_indices = [0] * n
	stack = [0]
	for i in range(1, n):
		while stack and a[i] >= a[stack[-1]]:
			stack.pop(-1)
		if stack:
			max_indices[i] = stack[-1] + 1
		else:
			max_indices[i] = 0
		stack.append(i)
	return max_indices

def max_index_product(a, n):
	lefts = closest_max(a, n)
	rights = closest_max(list(reversed(a)), n)
	rights.reverse()
	rights = [n + 1 - i if i != 0 else 0 for i in rights]
	return max((lefts[i] * rights[i] for i in range(n)))
n = int(input())
a = list(map(int, input().strip().split()))
print(max_index_product(a, n))


n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)


n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)


n = int(input())
a = [int(x) for x in input().strip().split(' ')]
l = [-1 for x in range(n)]
r = [-1 for x in range(n)]
(l[0], r[n - 1]) = (a[0], a[n - 1])
for x in range(1, n):
	l[x] = max(a[x], l[x - 1])
for x in range(n - 2, -1, -1):
	r[x] = max(a[x], r[x + 1])
maxv = 0
for i in range(1, n - 1):
	lr = 0
	if l[i - 1] <= a[i]:
		continue
	if r[i + 1] <= a[i]:
		continue
	(li, ri) = (i - 1, i + 1)
	for j in range(i - 1, -1, -1):
		if a[j] > a[i]:
			li = j
			break
	for j in range(i + 1, n):
		if a[j] > a[i]:
			ri = j
			break
	lr = (li + 1) * (ri + 1)
	if lr > maxv:
		maxv = lr
print(maxv)


n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)


n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)


def get_left(a):
	n = len(a)
	rv = [0] * n
	stack = []
	stack.append((10 ** 9 + 2, 0))
	for i in range(n):
		while True:
			x = stack[-1]
			if x[0] > a[i]:
				break
			stack.pop()
		rv[i] = stack[-1][1]
		stack.append((a[i], i + 1))
	return rv

def get_right(a):
	n = len(a)
	rv = [0] * n
	stack = []
	stack.append((10 ** 9 + 2, 0))
	for i in range(n - 1, -1, -1):
		while True:
			x = stack[-1]
			if x[0] > a[i]:
				break
			stack.pop()
		rv[i] = stack[-1][1]
		stack.append((a[i], i + 1))
	return rv
n = int(input())
a = [int(x) for x in input().split()]
left = get_left(a)
right = get_right(a)
m = [left[i] * right[i] for i in range(n)]
print(max(m))


ct = int(input())
arr = [int(x) for x in input().split(' ')]
left = []
right = []
left.append(0)
for n in range(2, ct + 1):
	test_index = n - 1
	val = arr[n - 1]
	test_val = arr[test_index - 1]
	while test_index > 0 and test_val <= val:
		if test_val <= val:
			test_index = left[test_index - 1]
			test_val = arr[test_index - 1]
	left.append(test_index)
right = [0] * ct
for n in range(ct - 1, 0, -1):
	test_index = n + 1
	val = arr[n - 1]
	test_val = arr[test_index - 1]
	while test_index > 0 and test_index <= ct and (test_val <= val):
		if test_val <= val:
			test_index = right[test_index - 1]
			test_val = arr[test_index - 1]
	right[n - 1] = test_index
max_index_product = -1
for n in range(ct):
	index_product = left[n] * right[n]
	max_index_product = max(index_product, max_index_product)
print(max_index_product)


n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)


N = input()
arr = list(map(int, input().split()))
L = []
R = []

def traverse_Stack(arr):
	lst = []
	Stack = []
	for i in range(int(N)):
		while len(Stack) != 0 and arr[i] >= arr[Stack[len(Stack) - 1]]:
			Stack.pop()
		if len(Stack) == 0:
			lst.append(0)
		else:
			lst.append(Stack[len(Stack) - 1] + 1)
		Stack.append(i)
	return lst

def max_product():
	L = traverse_Stack(arr)
	arr.reverse()
	R = traverse_Stack(arr)
	R = [len(R) + 1 - x if x > 0 else 0 for x in R]
	R.reverse()
	max_product = [L[i] * R[i] for i in range(int(N))]
	print(max(max_product))
if len(arr) == 1:
	print(0)
else:
	max_product()


n = int(input().strip())
a = [0] + list(map(int, input().strip().split()))
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(2, n + 1):
	p = i - 1
	while p > 0 and a[p] <= a[i]:
		p = left[p]
	left[i] = p
for i in range(n - 1, 0, -1):
	p = i + 1
	while p > 0 and a[p] <= a[i]:
		p = right[p]
	right[i] = p
ans = 0
for i in range(1, n + 1):
	ans = max(ans, left[i] * right[i])
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)


n = int(input().strip())
A = [int(a) for a in input().strip().split(' ')]
left = [0] * n
stack = []
for (i, a) in enumerate(A):
	while stack and a >= stack[-1][0]:
		stack.pop()
	if stack:
		left[i] = stack[-1][1] + 1
	stack.append((a, i))
right = [0] * n
stack = []
for (i, a) in enumerate(reversed(A)):
	while stack and a >= stack[-1][0]:
		stack.pop()
	if stack:
		right[i] = n - stack[-1][1]
	stack.append((a, i))
print(max((l * r for (l, r) in zip(left, reversed(right)))))


input()
mx = 0
st = [(float('inf'), 0, 0)]
for (j, a) in enumerate(map(int, input().split()), 1):
	while st[-1][0] < a:
		i = st.pop()[2]
		mx = max(i * j, mx)
	i = st[-1][2] if st[-1][0] == a else st[-1][1]
	st.append((a, j, i))
print(mx)


n = int(input())
lst = [int(i) for i in input().split(' ')]
left_max = 0
right_max = len(lst)
left_stack = []
right_stack = []
product = 0
for i in range(1, len(lst) - 1):
	value = lst[i]
	prev = lst[i - 1]
	if value < lst[i - 1]:
		left_max = i
		left_stack.append(left_max)
	elif left_max == 0:
		pass
	elif value > lst[i - 1] and value >= lst[left_max - 1]:
		while left_stack:
			index = left_stack.pop()
			if value < lst[index - 1]:
				left_max = index
				left_stack.append(index)
				break
			else:
				left_max = 0
	if left_max == 0:
		right_max = 0
		continue
	if value < lst[i - 1]:
		border = right_max - 1 if right_max else len(lst)
		for j in range(i + 1, border):
			if lst[j] > value:
				right_max = j + 1
				break
	elif value > lst[i - 1]:
		for j in range(right_max, len(lst)):
			if lst[j] > value:
				right_max = j + 1
				break
			else:
				right_max = 0
	if left_max * right_max > product:
		product = left_max * right_max
print(product)


n = int(input())
arr = list(map(int, input().split()))
current_max = [arr[0], 0]
ans = 0
s = []
for i in range(1, n):
	if arr[i] >= current_max[0] and (not s):
		current_max[0] = arr[i]
		current_max[1] = i
	elif not s:
		s.append([i, current_max[1]])
	elif arr[i] < arr[s[len(s) - 1][0]]:
		s.append([i, s[len(s) - 1][0]])
	else:
		while s and arr[i] > arr[s[len(s) - 1][0]]:
			el = s.pop()
			tmp_ans = (el[1] + 1) * (i + 1)
			if tmp_ans > ans:
				ans = tmp_ans
print(ans)


def find_rightmost_local_min(a, N):
	for i in range(N - 1, 1, -1):
		if a[i] > a[i - 1] and a[i - 1] <= a[i - 2]:
			return i - 1
	return 0

def maximize_product(a, N):
	k = find_rightmost_local_min(a, N)
	l = k - 1
	while l >= 0 and a[l] <= a[k]:
		l -= 1
	product = (l + 1) * (k + 2)
	r = k + 1
	while r < N - 1 and l > 0:
		if a[l] > a[r]:
			product = max(product, l * (r + 2))
			r += 1
		else:
			l -= 1
	return product
N = int(input().strip())
a = map(int, input().strip().split(' '))
print(maximize_product(list(map(int, a)), N))


N = int(input())
A = [int(x) for x in input().split()]
P = [0] * N
S = []
for i in range(N):
	while S and A[S[-1]] <= A[i]:
		S.pop()
	if S:
		P[i] = S[-1] + 1
	S.append(i)
S = []
for i in range(N - 1, -1, -1):
	while S and A[S[-1]] <= A[i]:
		S.pop()
	if S:
		P[i] *= S[-1] + 1
	else:
		P[i] = 0
	S.append(i)
print(max(P))


n = int(input())
a = list(map(int, input().strip().split()))
left = [0] * n
right = [0] * n
stk = []
for i in range(n):
	while stk and a[stk[-1]] <= a[i]:
		stk.pop()
	if stk:
		left[i] = stk[-1] + 1
	else:
		left[i] = 0
	stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
	while stk and a[stk[-1]] <= a[i]:
		stk.pop()
	if stk:
		right[i] = stk[-1] + 1
	else:
		right[i] = 0
	stk.append(i)
mx = 0
for i in range(n):
	ip = left[i] * right[i]
	if ip > mx:
		mx = ip
print(mx)


def maximum_index_product(numbers):
	left_stack = []
	right_stack = []
	left = [-1] * len(numbers)
	right = [-1] * len(numbers)
	for i in range(len(numbers)):
		while left_stack and numbers[left_stack[-1]] <= numbers[i]:
			left_stack.pop()
		if left_stack:
			left[i] = left_stack[-1]
		left_stack.append(i)
		j = len(numbers) - i - 1
		while right_stack and numbers[right_stack[-1]] <= numbers[j]:
			right_stack.pop()
		if right_stack:
			right[j] = right_stack[-1]
		right_stack.append(j)
	max_prod = 0
	for i in range(len(numbers)):
		max_prod = max(max_prod, (left[i] + 1) * (right[i] + 1))
	return max_prod
_ = input()
numbers = list(map(int, input().strip().split(' ')))
print(maximum_index_product(numbers))


def get_max(indicies, a, reverse=False):
	stack = []
	if not reverse:
		prev_num = a[0]
		for i in range(1, n):
			if prev_num > a[i]:
				stack.append(i - 1)
				indicies[i] = i - 1
			elif stack:
				if a[stack[-1]] > a[i]:
					indicies[i] = stack[-1]
				else:
					while stack:
						if a[stack[-1]] > a[i]:
							indicies[i] = stack[-1]
							break
						else:
							stack.pop(-1)
			prev_num = a[i]
	else:
		prev_num = a[-1]
		for i in range(n - 2, -1, -1):
			if prev_num > a[i]:
				stack.append(i + 1)
				indicies[i] = i + 1
			elif stack:
				if a[stack[-1]] > a[i]:
					indicies[i] = stack[-1]
				else:
					while stack:
						if a[stack[-1]] > a[i]:
							indicies[i] = stack[-1]
							break
						stack.pop(-1)
			prev_num = a[i]
	return indicies
n = int(input())
A = [int(w) for w in input().split()]
left_indicies = [-1] * n
right_indicies = [-1] * n
print(max([(a + 1) * (b + 1) for (a, b) in zip(get_max(left_indicies, A), get_max(right_indicies, A, True))]))


import sys
import math
n = int(sys.stdin.readline())
nums = [int(x) for x in sys.stdin.readline().split()]
left = [0] * len(nums)
stack = []
for (idx, num) in reversed(list(enumerate(nums))):
	while len(stack) > 0 and num > stack[-1][1]:
		(other_idx, _) = stack.pop()
		left[other_idx] = idx + 1
	stack.append((idx, num))
right = [0] * len(nums)
stack = []
for (idx, num) in enumerate(nums):
	while len(stack) > 0 and num > stack[-1][1]:
		(other_idx, _) = stack.pop()
		right[other_idx] = idx + 1
	stack.append((idx, num))
index_product = [x * y for (x, y) in zip(left, right)]
print(max(index_product))


n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)


tamanio = int(input())
maximo = 0
elementos = [int(i) for i in input().split()]
arreglo = [[-1, -1] for i in range(tamanio)]
for i in range(1, tamanio):
	apuntar = i - 1
	while apuntar > -1:
		if elementos[apuntar] > elementos[i]:
			arreglo[i][0] = apuntar
			break
		apuntar = arreglo[apuntar][0]
for i in range(tamanio - 2, -1, -1):
	apuntar = i + 1
	while apuntar > -1:
		if elementos[apuntar] > elementos[i]:
			arreglo[i][1] = apuntar
			break
		apuntar = arreglo[apuntar][1]
for i in range(1, tamanio):
	if arreglo[i][0] != -1 and arreglo[i][1] != -1:
		tmp = (arreglo[i][0] + 1) * (arreglo[i][1] + 1)
		if tmp > maximo:
			maximo = tmp
print(maximo)


n = int(input())
a_s = list(map(int, input().strip().split(' ')))
lefts = [None]
stack = []

def find_rightmost_local_min(a, N):
	for i in range(N - 1, 1, -1):
		if a[i] > a[i - 1] and a[i - 1] <= a[i - 2]:
			return i - 1
	return 0

def maximize_product(a, N):
	k = find_rightmost_local_min(a, N)
	l = k - 1
	while l >= 0 and a[l] <= a[k]:
		l -= 1
	product = (l + 1) * (k + 2)
	r = k + 1
	while r < N - 1 and l > 0:
		if a[l] > a[r]:
			product = max(product, l * (r + 2))
			r += 1
		else:
			l -= 1
	return product
print(maximize_product(a_s, n))


import sys

def left(i, arr, jump):
	index = i - 1
	while index >= 0:
		if arr[index] > arr[i]:
			jump[arr[i]] = index
			return index + 1
		elif arr[index] in jump and jump[arr[index]] < i:
			index = jump[arr[index]]
		else:
			index -= 1
	jump[arr[i]] = -1
	return 0

def right(i, arr, jump):
	index = i + 1
	while index < len(arr):
		if arr[index] > arr[i]:
			jump[arr[i]] = index
			return index + 1
		elif arr[index] in jump and jump[arr[index]] > i:
			index = jump[arr[index]]
		else:
			index += 1
	jump[arr[i]] = len(arr)
	return 0

def maxIndexProduct(n, arr):
	max_indexProduct = 0
	dict_left_jump = {}
	dict_right_jump = {}
	for i in range(1, n - 1):
		indexProduct_i = left(i, arr, dict_left_jump) * right(i, arr, dict_right_jump)
		if indexProduct_i > max_indexProduct:
			max_indexProduct = indexProduct_i
	return max_indexProduct
n = int(input().strip())
arr = list(map(int, input().strip().split(' ')))
print(maxIndexProduct(n, arr))


def indexProduct(arr):
	stack = []
	left = [0 for x in range(len(arr))]
	for i in range(len(arr)):
		if not stack:
			left[i] = 0
			stack.append((arr[i], i + 1))
		elif arr[i] < stack[-1][0]:
			left[i] = stack[-1][1]
			stack.append((arr[i], i + 1))
		else:
			while len(stack) > 0 and arr[i] >= stack[-1][0]:
				stack.pop()
			if len(stack) == 0:
				left[i] = 0
			else:
				left[i] = stack[-1][1]
			stack.append((arr[i], i + 1))
	res = 0
	stack = []
	for i in range(len(arr) - 1, -1, -1):
		if not stack:
			res = max(res, 0)
			stack.append((arr[i], i + 1))
		elif arr[i] < stack[-1][0]:
			res = max(res, left[i] * stack[-1][1])
			stack.append((arr[i], i + 1))
		else:
			while len(stack) > 0 and arr[i] >= stack[-1][0]:
				stack.pop()
			if len(stack) == 0:
				res = max(res, 0)
			else:
				res = max(res, left[i] * stack[-1][1])
			stack.append((arr[i], i + 1))
	return res
n = int(input())
arr = list(map(int, input().split(' ')))
print(indexProduct(arr))


import sys

def find_left(arr):
	lstack = [1]
	output = []
	for ind in range(1, len(arr) - 1):
		while lstack and arr[lstack[-1] - 1] <= arr[ind]:
			lstack.pop()
		left = lstack[-1] if lstack else 0
		lstack.append(ind + 1)
		output.append(left)
	return output

def find_right(arr):
	arr_len = len(arr)
	rstack = [1]
	output = []
	for ind in range(1, len(arr) - 1):
		while rstack and arr[rstack[-1] - 1] <= arr[ind]:
			rstack.pop()
		right = arr_len - rstack[-1] + 1 if rstack else 0
		rstack.append(ind + 1)
		output.append(right)
	return output[::-1]

def solution(arr):
	res = 0
	left = find_left(arr)
	right = find_right(arr[::-1])
	for el in zip(left, right):
		res = max(res, el[0] * el[1])
	return res
n = int(input().strip())
arr = [int(x) for x in input().strip().split()]
print(solution(arr))


class Stack:

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

	def isEmpty(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[len(self.items) - 1]

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

	def printme(self):
		return self.items
n = int(input())
lst = [int(x) for x in input().split()]
left = []
right = []
lst2 = []
for i in range(n):
	left.append(0)
	right.append(0)
	lst2.append((lst[i], i + 1))
s = Stack()
s.push(lst2[0])
for i in range(1, n):
	(currVal, currIndex) = lst2[i]
	(topVal, topIndex) = s.peek()
	if currVal <= topVal:
		s.push((currVal, currIndex))
		continue
	while not s.isEmpty() and currVal > topVal:
		(val, ind) = s.pop()
		right[ind - 1] = currIndex
		if not s.isEmpty():
			(topVal, topIndex) = s.peek()
	s.push((currVal, currIndex))
s = Stack()
s.push(lst2[-1])
for i in range(n - 2, -1, -1):
	(currVal, currIndex) = lst2[i]
	(topVal, topIndex) = s.peek()
	if currVal <= topVal:
		s.push((currVal, currIndex))
		continue
	while not s.isEmpty() and currVal > topVal:
		(val, ind) = s.pop()
		left[ind - 1] = currIndex
		if not s.isEmpty():
			(topVal, topIndex) = s.peek()
	s.push((currVal, currIndex))
ans = 0
for i in range(n):
	t = left[i] * right[i]
	if t > ans:
		ans = t
print(ans)


class linked_list(object):

	def __init__(self, key, index):
		self.key = key
		self.index = index
		self.previous = None
		self.next = None
n = int(input())
arr = list(map(int, input().split()))
que = linked_list(arr[0], 0)
front_back = []
result = 0
for i in range(len(arr)):
	cur = que
	while cur.key <= arr[i] and cur.previous != None:
		cur = cur.previous
	if cur.key > arr[i]:
		front_back.append(cur.index + 1)
	else:
		front_back.append(0)
	if cur.key == arr[i]:
		cur.index = i
		que = cur
	else:
		new_element = linked_list(arr[i], i)
		cur.next = new_element
		new_element.previous = cur
		que = new_element
que = linked_list(arr[-1], len(arr) - 1)
for i in reversed(range(0, len(arr))):
	cur = que
	while cur.key < arr[i] and cur.previous != None:
		cur = cur.previous
	if cur.key > arr[i]:
		result = max(result, front_back[i] * (cur.index + 1))
	if cur.key == arr[i]:
		cur.index = i
		que = cur
	else:
		new_element = linked_list(arr[i], i)
		cur.next = new_element
		new_element.previous = cur
		que = new_element
print(result)


def find_rightmost_local_min(a, N):
	for i in range(N - 1, 1, -1):
		if a[i] > a[i - 1] and a[i - 1] <= a[i - 2]:
			return i - 1
	return 0

def maximize_product(a, N):
	k = find_rightmost_local_min(a, N)
	l = k - 1
	while l >= 0 and a[l] <= a[k]:
		l -= 1
	product = (l + 1) * (k + 2)
	r = k + 1
	while r < N - 1 and l > 0:
		if a[l] > a[r]:
			product = max(product, l * (r + 2))
			r += 1
		else:
			l -= 1
	return product
N = int(input().strip())
a = list(map(int, input().strip().split(' ')))
print(maximize_product(a, N))


import bisect
n = int(input())
l = list(map(int, input().split(' ')))
a = []
ll = []
for i in range(n):
	while len(a) > 0 and a[-1][0] <= l[i]:
		a.pop()
	if len(a) > 0:
		ll.append(a[-1][1])
	else:
		ll.append(0)
	a.append((l[i], i + 1))
a = []
rr = []
for i in range(n - 1, -1, -1):
	while len(a) > 0 and a[-1][0] <= l[i]:
		a.pop()
	if len(a) > 0:
		rr.append(a[-1][1])
	else:
		rr.append(0)
	a.append((l[i], i + 1))
m = 0
for i in range(n):
	m = max(m, ll[i] * rr[n - 1 - i])
print(m)


import sys
from time import time
import bisect

def solve_slow(aa):

	def interval_gen(aa, op):
		(last, i) = (aa[0], 1)
		(fr, to) = (None, None)
		while i != len(aa):
			(fr, to) = (i - 1, None)
			while i != len(aa) and (not op(aa[i], last)):
				last = aa[i]
				i += 1
			to = i - 1
			if fr != to:
				yield (fr, to)
				(fr, to) = (None, None)
			while i != len(aa) and op(aa[i], last):
				last = aa[i]
				i += 1
		if to is not None:
			yield (fr, to)

	def calc_right(aa, i, ff, cache):
		ix = bisect.bisect_right(ff, i)
		(fr, to) = cache[ix - 1]
		if i < to:
			return i + 1
		for j in range(ix, len(cache)):
			(fr, to) = cache[j]
			if aa[to] > aa[i]:
				if aa[fr] > aa[i]:
					return fr
				while to - fr > 1:
					m = (fr + to) // 2
					if aa[m] <= aa[i]:
						fr = m
					else:
						to = m
				return to
		return None

	def calc_left(aa, i, ff, cache):
		ix = bisect.bisect_right(ff, i)
		if ix == 0:
			return None
		(fr, to) = cache[ix - 1]
		if i <= to and i > fr:
			return i - 1
		for j in range(ix - 1, -1, -1):
			(fr, to) = cache[j]
			if aa[fr] > aa[i]:
				while to - fr > 1:
					m = (fr + to) // 2
					if aa[m] > aa[i]:
						fr = m
					else:
						to = m
				return fr
		return None
	icache = tuple((t for t in interval_gen(aa, lambda a, b: a <= b)))
	dcache = tuple((t for t in interval_gen(aa, lambda a, b: a >= b)))
	iff = [fr for (fr, _) in icache]
	dff = [fr for (fr, _) in dcache]
	mx = 0
	for i in range(len(aa)):
		l = calc_left(aa, i, dff, dcache)
		r = calc_right(aa, i, iff, icache)
		if l is None or r is None:
			p = 0
		else:
			p = (l + 1) * (r + 1)
		if mx < p:
			mx = p
	return mx

def solve(aa):

	def left_gen(aa):
		cache = []
		for (i, a) in enumerate(aa):
			print('\t\ti=%d cache=%s' % (i, cache), file=sys.stderr)
			if not cache:
				yield (i, None)
				cache.append(i)
			elif a < aa[cache[-1]]:
				yield (i, cache[-1])
				cache.append(i)
			elif a == aa[cache[-1]]:
				cache[-1] = i
				if len(cache) > 1:
					yield (i, cache[-2])
				else:
					yield (i, None)
			else:
				while cache and aa[cache[-1]] <= a:
					cache.pop()
				if not cache:
					yield (i, None)
				else:
					yield (i, cache[-1])
				cache.append(i)

	def right_gen(aa):
		cache = []
		for i in range(len(aa) - 1, -1, -1):
			a = aa[i]
			if not cache:
				yield (i, None)
				cache.append(i)
			elif a < aa[cache[-1]]:
				yield (i, cache[-1])
				cache.append(i)
			elif a == aa[cache[-1]]:
				cache[-1] = i
				if len(cache) > 1:
					yield (i, cache[-2])
				else:
					yield (i, None)
			else:
				while cache and aa[cache[-1]] <= a:
					cache.pop()
				if not cache:
					yield (i, None)
				else:
					yield (i, cache[-1])
				cache.append(i)
	pp = [1] * len(aa)
	for (i, ix) in left_gen(aa):
		print('\ti=%d ix=%s' % (i, ix), file=sys.stderr)
		if ix is None:
			pp[i] = 0
		else:
			pp[i] *= ix + 1
	for (i, ix) in right_gen(aa):
		print('\ti=%d ix=%s' % (i, ix), file=sys.stderr)
		if ix is None:
			pp[i] = 0
		else:
			pp[i] *= ix + 1
	print('\tpp=%s' % (pp,), file=sys.stderr)
	return max(pp)
tm = time()
_ = int(input())
aa = list(map(int, input().split()))
print(solve(aa))
print('time elapsed: %s' % (time() - tm,), file=sys.stderr)


ln = int(input())
l = list(map(int, input().split()))
right = [0 for i in range(len(l))]
st = [0]
for i in range(1, len(l)):
	while st and l[st[-1]] < l[i]:
		j = st[-1]
		right[j] = i + 1
		st.pop()
	st.append(i)
left = [0 for i in range(len(l))]
st = [ln - 1]
for i in range(ln - 2, -1, -1):
	while st and l[st[-1]] < l[i]:
		j = st[-1]
		left[j] = i + 1
		st.pop()
	st.append(i)
ans = left
for i in range(ln):
	left[i] *= right[i]
print(max(ans))


n = int(input())
a = [0] + list(map(int, input().split()))
l = [0] * (n + 1)
r = [0] * (n + 1)
m = 0
for i in range(1, n + 1):
	d = i - 1
	while d >= 1:
		if a[d] > a[i]:
			l[i] = d
			break
		else:
			d = l[d]
for i in range(n, 0, -1):
	d = i + 1
	while d <= n and d > 0:
		if a[d] > a[i]:
			r[i] = d
			break
		else:
			d = r[d]
for i in range(1, n):
	if l[i] == 0 or r[i] == 0:
		continue
	ans = l[i] * r[i]
	if ans > m:
		m = ans
print(m)


n = int(input())
nums = list(map(int, input().split()))
stack = []
left = []
for (i, n) in enumerate(nums):
	while stack and n >= stack[-1][1]:
		stack.pop()
	left.append(stack[-1][0] if stack else 0)
	stack.append((i + 1, n))
stack = []
right = []
for (i, n) in reversed(list(enumerate(nums))):
	while stack and n >= stack[-1][1]:
		stack.pop()
	right.append(stack[-1][0] if stack else 0)
	stack.append((i + 1, n))
right = right[::-1]
print(max((l * r for (l, r) in zip(left, right))))


import os
import sys
n = int(input())
a = list(map(int, input().split()))
a.insert(0, None)
left = {}
right = {}
left[1] = 0
right[n] = 0
for i in range(2, n + 1):
	if a[i] == a[i - 1]:
		left[i] = left[i - 1]
	elif a[i] < a[i - 1]:
		left[i] = i - 1
	elif left[i - 1] == 0:
		left[i] = 0
	else:
		counter = i - 1
		while True:
			leftNumber = a[left[counter]]
			if left[counter] == 1:
				if a[1] > a[i]:
					left[i] = 1
				else:
					left[i] = 0
				break
			if leftNumber == a[i]:
				left[i] = left[left[counter]]
				break
			elif leftNumber > a[i]:
				left[i] = left[counter]
				break
			elif left[left[counter]] == 0:
				left[i] = 0
				break
			else:
				counter = left[counter]
for i in range(n - 1, 0, -1):
	if a[i] == a[i + 1]:
		right[i] = right[i + 1]
	elif a[i] < a[i + 1]:
		right[i] = i + 1
	elif right[i + 1] == 0:
		right[i] = 0
	else:
		counter = i + 1
		while True:
			rightNumber = a[right[counter]]
			if right[counter] == n:
				if a[n] > a[i]:
					right[i] = n
				else:
					right[i] = 0
				break
			if rightNumber == a[i]:
				right[i] = right[right[counter]]
				break
			elif rightNumber > a[i]:
				right[i] = right[counter]
				break
			elif right[right[counter]] == 0:
				right[i] = 0
				break
			else:
				counter = right[counter]
maxProduct = 0
for i in range(1, n):
	product = left[i] * right[i]
	if maxProduct < product:
		maxProduct = product
print(maxProduct)