Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, insort_left
N = int(input())
A = list(map(int, raw_input().split()))


# 各数の出現場所を持ってソート: 1-indexed
A_with_position = sorted([[a, i] for i, a in enumerate(A, start=1)])


# 出現したもののindex
appeared_index = [0, N + 1]

ans = 0
for a, i in A_with_position:
    li = bisect_left(appeared_index, i) - 1
    ri = bisect_left(appeared_index, i)

    lx, rx = appeared_index[li], appeared_index[ri]
    ans += a * (i - lx) * (rx - i)

    insort_left(appeared_index, i)

print(ans)


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

d = [0] * (N+1)
for i in range(N):
    d[a[i]] = i

left = list(range(N+1))
right = list(range(N+1))

ans = 0
for i in range(N, 0, -1):
    di = d[i]
    ans += i * (right[di]-di+1) * (di-left[di]+1)
    right[left[di] - 1] = right[di]
    left[right[di] + 1] = left[di]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, insort_left
N = int(input())
A = list(map(int, input().split()))


# 各数の出現場所を持ってソート: 1-indexed
A_with_position = sorted([[a, i] for i, a in enumerate(A, start=1)])


# 出現したもののindex
appeared_index = [0, N + 1]

ans = 0
for a, i in A_with_position:
    li = bisect_left(appeared_index, i) - 1
    ri = bisect_left(appeared_index, i)

    lx, rx = appeared_index[li], appeared_index[ri]
    ans += a * (i - lx) * (rx - i)

    insort_left(appeared_index, i)

print(ans)


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

d = [0] * (N+1)
for i in range(N):
    d[a[i]] = i

left = list(range(N+1))
right = list(range(N+1))

ans = 0
for i in range(N, 0, -1):
    di = d[i]
    ans += i * (right[di]-di+1) * (di-left[di]+1)
    right[left[di] - 1] = right[di]
    left[right[di] + 1] = left[di]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, insort_left
N = int(input())
A = list(map(int, input().split()))


# 各数の出現場所を持ってソート: 1-indexed
A_with_position = sorted([[a, i] for i, a in enumerate(A, start=1)])


# 出現したもののindex
appeared_index = [0, N + 1]

ans = 0
for a, i in A_with_position:
    li = bisect_left(appeared_index, i) - 1
    ri = bisect_left(appeared_index, i)
    
    lx, rx = appeared_index[li], appeared_index[ri]
    ans += a * (i - lx) * (rx - i)

    insort_left(appeared_index, i)

print(ans)


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

d = [0] * (N+1)
for i in range(N):
    d[a[i]] = i

left = list(range(N+1))
right = list(range(N+1))

ans = 0
for i in range(N, 0, -1):
    di = d[i]
    ans += i * (right[di]-di+1) * (di-left[di]+1)
    right[left[di] - 1] = right[di]
    left[right[di] + 1] = left[di]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))


    class RangeMinimumQuery:
        def __init__(self, n, inf=2 ** 31 - 1):
            self.n = 1 << (n - 1).bit_length()
            self.INF = inf
            self.segtree = [self.INF] * (2 * self.n)

        # i番目の値(0-indexed)をxに変更
        def update(self, i, x):
            i += self.n
            self.segtree[i] = x
            while i > 0:
                i //= 2
                self.segtree[i] = min(self.segtree[2 * i], self.segtree[2 * i + 1])

        # [l, r)のmin
        def query(self, l, r):
            L, R = l + self.n, r + self.n
            R = min(R, len(self.segtree))
            s = self.INF
            while L < R:
                if L & 1:
                    s = min(s, self.segtree[L])
                    L += 1

                if R & 1:
                    s = min(s, self.segtree[R - 1])
                    R -= 1

                L >>= 1
                R >>= 1

            return s


    # 番兵を設置
    A = [0] + A + [0]
    N = N + 2


    # セグ木を初期化
    RMQ = RangeMinimumQuery(N)
    for i, a in enumerate(A):
        RMQ.update(i, a)


    # r_indexes := 自分より右側であって、最も近い、自分より小さなもののindex
    # l_indexes := 自分より左側であって、最も近い、自分より小さなもののindex
    r_indexes = [None] * N
    l_indexes = [None] * N


    # 右側についてにぶたん := iからm内の区間最小値がai以上か？
    for i, a in enumerate(A[1: -1], start=1):
        ok, ng = i, N - 1
        while abs(ok - ng) > 1:
            m = (ok + ng) // 2

            if a <= RMQ.query(i, m + 1):
                ok = m
            else:
                ng = m

        r_indexes[i] = ok + 1

    # 左側についてにぶたん := iからm内の区間最小値がai以上か？
    for i, a in enumerate(A[1: -1], start=1):
        ok, ng = i, 0
        while abs(ok - ng) > 1:
            m = (ok + ng) // 2

            if a <= RMQ.query(m, i + 1):
                ok = m
            else:
                ng = m

        l_indexes[i] = ok - 1


    # 答えを計算
    ans = 0
    for i, (a, l, r) in enumerate(zip(A[1: -1], l_indexes[1: -1], r_indexes[1: -1]), start=1):
        ans += a * (i - l) * (r - i)

    print(ans)


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

d = [0] * (N+1)
for i in range(N):
    d[a[i]] = i

left = list(range(N+1))
right = list(range(N+1))

ans = 0
for i in range(N, 0, -1):
    di = d[i]
    ans += i * (right[di]-di+1) * (di-left[di]+1)
    right[left[di] - 1] = right[di]
    left[right[di] + 1] = left[di]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))


class RangeMinimumQuery:
    def __init__(self, n, inf=2 ** 31 - 1):
        self.n = 1 << (n - 1).bit_length()
        self.INF = inf
        self.segtree = [self.INF] * (2 * self.n)

    # i番目の値(0-indexed)をxに変更
    def update(self, i, x):
        i += self.n
        self.segtree[i] = x
        while i > 0:
            i //= 2
            self.segtree[i] = min(self.segtree[2 * i], self.segtree[2 * i + 1])

    # [l, r)のmin
    def query(self, l, r):
        L, R = l + self.n, r + self.n
        R = min(R, len(self.segtree))
        s = self.INF
        while L < R:
            if L & 1:
                s = min(s, self.segtree[L])
                L += 1

            if R & 1:
                s = min(s, self.segtree[R - 1])
                R -= 1

            L >>= 1
            R >>= 1

        return s


# 番兵を設置
A = [0] + A + [0]
N = N + 2


# セグ木を初期化
RMQ = RangeMinimumQuery(N)
for i, a in enumerate(A):
    RMQ.update(i, a)


# r_indexes := 自分より右側であって、最も近い、自分より小さなもののindex
# l_indexes := 自分より左側であって、最も近い、自分より小さなもののindex
r_indexes = [None] * N
l_indexes = [None] * N


# 右側についてにぶたん := iからm内の区間最小値がai以上か？
for i, a in enumerate(A[1: -1], start=1):
    ok, ng = i, N - 1
    while abs(ok - ng) > 1:
        m = (ok + ng) // 2

        if a <= RMQ.query(i, m + 1):
            ok = m
        else:
            ng = m

    r_indexes[i] = ok + 1

# 左側についてにぶたん := iからm内の区間最小値がai以上か？
for i, a in enumerate(A[1: -1], start=1):
    ok, ng = i, 0
    while abs(ok - ng) > 1:
        m = (ok + ng) // 2

        if a <= RMQ.query(m, i + 1):
            ok = m
        else:
            ng = m

    l_indexes[i] = ok - 1


# 答えを計算
ans = 0
for i, (a, l, r) in enumerate(zip(A[1: -1], l_indexes[1: -1], r_indexes[1: -1]), start=1):
    ans += a * (i - l) * (r - i)

print(ans)


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

d = [0] * (N+1)
for i in range(N):
    d[a[i]] = i

left = list(range(N+1))
right = list(range(N+1))

ans = 0
for i in range(N, 0, -1):
    di = d[i]
    ans += i * (right[di]-di+1) * (di-left[di]+1)
    right[left[di] - 1] = right[di]
    left[right[di] + 1] = left[di]

print(ans)