Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2*10**5)

n = int(input())
a = list(map(int, input().split()))
# aのindexを前計算
d = {}
for i,j in enumerate(a):
    d[j] = i


# segtree
data = [float("inf")]*(2*n)
# a_k の値を x に更新
def update(k, x):
    k += n-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + n; R = r + n
    s = float("inf")
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

# initialize
for i, j in enumerate(a):
    update(i,j)

# 区間[left, right)が与えられた場合の和を求める再帰
def rec(left=0, right=n):
    if left==right:
        return 0
    # O(logN)
    min_ = query(left, right)
    ind = d[min_]
    res = min_*(right-ind)*(ind+1-left)
    res += rec(left, ind)
    res += rec(ind+1,right)
    return res

print(rec())

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
d = {}
for i,j in enumerate(a):
    d[j] = i

uf = [-1]*n
def root(a):
    if uf[a] < 0:
        return a
    uf[a] = root(uf[a])
    return uf[a]
def unite(a,b):
    ra,rb = root(a),root(b)
    if ra==rb:
        return False
    if uf[ra] > uf[rb]:
        ra,rb = rb,ra
    uf[ra] += uf[rb]
    uf[rb] = ra
    return True

ans = 0
for i in range(n,0,-1):
    left=right=0
    ind = d[i]

    if ind<n-1 and a[ind] < a[ind+1]:
        right -= uf[root(ind+1)]
        unite(ind, ind+1)
    if ind>0 and a[ind] < a[ind-1]:
        left -= uf[root(ind-1)]
        unite(ind, ind-1)
    ans += i*(left+1)*(right+1)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(2*10**5)

n = int(input())
a = list(map(int, input().split()))
# aのindexを前計算
d = {}
for i,j in enumerate(a):
    d[j] = i


# segtree
data = [float("inf")]*(2*n)
# a_k の値を x に更新
def update(k, x):
    k += n-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + n; R = r + n
    s = float("inf")
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

# initialize
for i, j in enumerate(a):
    update(i,j)

# 区間[left, right)が与えられた場合の和を求める再帰
def rec(left=0, right=n):
    if left==right:
        return 0
    min_ = query(left, right)
    ind = d[min_]
    res = min_*(right-ind)*(ind+1-left)
    res += rec(left, ind)
    res += rec(ind+1,right)
    return res

print(rec())

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
d = {}
for i,j in enumerate(a):
    d[j] = i

uf = [-1]*n
def root(a):
    if uf[a] < 0:
        return a
    uf[a] = root(uf[a])
    return uf[a]
def unite(a,b):
    ra,rb = root(a),root(b)
    if ra==rb:
        return False
    if uf[ra] > uf[rb]:
        ra,rb = rb,ra
    uf[ra] += uf[rb]
    uf[rb] = ra
    return True

ans = 0
for i in range(n,0,-1):
    left=right=0
    ind = d[i]

    if ind<n-1 and a[ind] < a[ind+1]:
        right -= uf[root(ind+1)]
        unite(ind, ind+1)
    if ind>0 and a[ind] < a[ind-1]:
        left -= uf[root(ind-1)]
        unite(ind, ind-1)
    ans += i*(left+1)*(right+1)

print(ans)