Submission #16085278

---

Source Code Expand

N = int(input())
a = list(map(int, input().split()))

left = [0] * (N + 1)
right = [0] * (N + 1)

# 左から
buf = list()
for i in range(N):
    while len(buf) > 0 and a[buf[-1]] > a[i]:
        buf.pop()
    if len(buf) > 0:
        left[i] = buf[-1]
    else:
        left[i] = -1
    buf.append(i)

# 右から
buf = list()
for i in reversed(range(N)):
    while len(buf) > 0 and a[buf[-1]] > a[i]:
        buf.pop()
    if len(buf) > 0:
        right[i] = buf[-1]
    else:
        right[i] = N
    buf.append(i)

ans = 0
for i in range(N):
    ans += a[i] * (i - left[i]) * (right[i] - i)

print(ans)

Submission Info

Judge Result