Задача "Гистограмма"

a = list(map(int, input().split()))
n = len(a)
 
 
st = [0]
ans_r = [n] * n 
 
for i in range(1, n):
    if a[i] > a[st[-1]]:
        st.append(i)
        continue
    while a[st[-1]] > a[i]:
        ans_r[st.pop()] = i
        if len(st) == 0:
            break
    st.append(i)
 
 
st = [0]
ans_l = [n] * n
a_1 = a[::-1]
 
for i in range(1, n):
    if a_1[i] > a_1[st[-1]]:
        st.append(i)
        continue
    while a_1[st[-1]] > a_1[i]:
        ans_l[st.pop()] = i
        if len(st) == 0:
            break
    st.append(i)
ans_l = ans_l[::-1]
 
for i in range(n):
    ans_l[i] = n - ans_l[i] - 1
 
 
m = 0
for i in range(n):
    g = a[i] * (ans_r[i] - ans_l[i] - 1)
    if m < g:
        m = g
# print(ans)
print(m)

x=list(map(int,input().split()))
n=x[0]
const=int(2e9)+1
h=[-const]+x[1:]+[-const]
prav=[0]*(n+2)
lev=[0]*(n+2)
st1=[0]
st2=[0]
for i in range(1,n+2):
    while h[st1[-1]]>h[i]:
        if i==n+1:
            prav[st1.pop()]=n+1
        else:
            prav[st1.pop()]=i
    st1.append(i)
    while h[st2[-1]]>h[-(i+1)]:
        if n-i+1!=0:
            lev[st2.pop()]=n-i+1
        else:
            lev[st2.pop()]=0
    st2.append(-(i+1))
bestS=0
for i in range(1,len(h)-1):
    if h[i]*(prav[i]-lev[i]-1)>bestS:
        bestS=h[i]*(prav[i]-lev[i]-1)
print(bestS)