Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)
 
input = sys.stdin.buffer.readline

class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    seg = SegTree(N, min, N+1)
    B = [0]*N
    for i, v in enumerate(A):
        B[i] = (i, A[i])
    B.sort(key=lambda x: x[1])
    ans = 0
    for index, v in B:
        seg.update(index, 1)
        left = seg.find_max_index(0, index, 1)
        right = seg.find_min_index(index+1, N, 1)
        if right == -1:
            right = N
        ans += v*(index-left)*(right-index)
    print(ans)
if __name__=="__main__":
    main()

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
 
input = sys.stdin.buffer.readline

class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    seg = SegTree(N, min, N+1)
    B = [0]*N
    for i, v in enumerate(A):
        B[i] = (i, A[i])
    B.sort(key=lambda x: x[1])
    ans = 0
    for index, v in B:
        seg.update(index, 1)
        left = seg.find_max_index(0, index, 1)
        right = seg.find_min_index(index+1, N, 1)
        if right == -1:
            right = N
        ans += v*(index-left)*(right-index)
    print(ans)
if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# segment tree verify
class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)


N = int(input())
A = list(map(int, input().split()))
seg = SegTree(N, min, N+1)
B = [0]*N
for i, v in enumerate(A):
    B[i] = (i, A[i])
B.sort(key=lambda x: x[1])
ans = 0
for index, v in B:
    seg.update(index, 1)
    left = seg.find_max_index(0, index, 1)
    right = seg.find_min_index(index+1, N, 1)
    if right == -1:
        right = N
    ans += v*(index-left)*(right-index)
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
 
input = sys.stdin.buffer.readline

class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    seg = SegTree(N, min, N+1)
    B = [0]*N
    for i, v in enumerate(A):
        B[i] = (i, A[i])
    B.sort(key=lambda x: x[1])
    ans = 0
    for index, v in B:
        seg.update(index, 1)
        left = seg.find_max_index(0, index, 1)
        right = seg.find_min_index(index+1, N, 1)
        if right == -1:
            right = N
        ans += v*(index-left)*(right-index)
    print(ans)
if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):

class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)


N = int(input())
A = list(map(int, input().split()))
seg = SegTree(N, min, N+1)
B = [0]*N
for i, v in enumerate(A):
    B[i] = (i, A[i])
B.sort(key=lambda x: x[1])
ans = 0
for index, v in B:
    seg.update(index, 1)
    left = seg.find_max_index(0, index, 1)
    right = seg.find_min_index(index+1, N, 1)
    if right == -1:
        right = N
    ans += v*(index-left)*(right-index)
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
 
input = sys.stdin.buffer.readline

class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    seg = SegTree(N, min, N+1)
    B = [0]*N
    for i, v in enumerate(A):
        B[i] = (i, A[i])
    B.sort(key=lambda x: x[1])
    ans = 0
    for index, v in B:
        seg.update(index, 1)
        left = seg.find_max_index(0, index, 1)
        right = seg.find_min_index(index+1, N, 1)
        if right == -1:
            right = N
        ans += v*(index-left)*(right-index)
    print(ans)
if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# segment tree verify
class SegTree():
    # 1-indexed
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X] = v
        for i in range(X-1, 0, -1):
            self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)


N = int(input())
A = list(map(int, input().split()))
seg = SegTree([N+1]*N, min, N+1)
B = [0]*N
for i, v in enumerate(A):
    B[i] = (i, A[i])

B.sort(key=lambda x: x[1])
ans = 0
for index, v in B:
    seg.update(index, 1)
    left = seg.find_max_index(0, index, 1)
    right = seg.find_min_index(index+1, N, 1)

    if right == -1:
        right = N
    ans += v*(index-left)*(right-index)
print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
 
input = sys.stdin.buffer.readline

class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    seg = SegTree(N, min, N+1)
    B = [0]*N
    for i, v in enumerate(A):
        B[i] = (i, A[i])
    B.sort(key=lambda x: x[1])
    ans = 0
    for index, v in B:
        seg.update(index, 1)
        left = seg.find_max_index(0, index, 1)
        right = seg.find_min_index(index+1, N, 1)
        if right == -1:
            right = N
        ans += v*(index-left)*(right-index)
    print(ans)
if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# bitの改造
import sys
input = sys.stdin.readline


class BIT:
    # 1,,,,,,,Nまでの数値を扱える
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def to_sum(self, i):
        # i番目のところまで要素を足し合わせる
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        # i 番目のところに要素を足し合わせる
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        # i番目からj番目までの要素の合計値を数える(1<=i<=j<=Nという制約がついているけど)
        return self.to_sum(j)-self.to_sum(i-1)

    def bisect_right(self, i):
        # i 番目から　次に初めて1増えるところまでの最大の値 j を求める
        l = i
        r = self.n
        if self.get(i, r) == r-i+1:
            return r
        while r-l > 1:
            M = (l+r)//2
            if self.get(i, M) < M-i+1:
                r = M
            else:
                l = M
        return l

    def bisect_left(self, i):
        # i 番目から最後に初めて1減るところまでの最小のjを求める
        l = 1
        r = i
        if self.get(l, i) == i+1-l:
            return l
        while r-l > 1:
            M = (r+l)//2
            if self.get(M, i) < i+1-M:
                l = M
            else:
                r = M
        return r


def main():
    N = int(input())
    a = list(map(int, input().split()))
    b = [(a[i], i+1) for i in range(N)]
    b.sort(reverse=True)
    tree = BIT(N)
    ans = 0

    for value, index in b:
        tree.add(index, 1)

        ans += (tree.bisect_right(index)-index+1) * \
            (index-tree.bisect_left(index)+1)*value

    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
 
input = sys.stdin.buffer.readline

class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    seg = SegTree(N, min, N+1)
    B = [0]*N
    for i, v in enumerate(A):
        B[i] = (i, A[i])
    B.sort(key=lambda x: x[1])
    ans = 0
    for index, v in B:
        seg.update(index, 1)
        left = seg.find_max_index(0, index, 1)
        right = seg.find_min_index(index+1, N, 1)
        if right == -1:
            right = N
        ans += v*(index-left)*(right-index)
    print(ans)
if __name__=="__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# bitの改造
import sys
input = sys.stdin.readline


class BIT:
    # 1,,,,,,,Nまでの数値を扱える
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def to_sum(self, i):
        # i番目のところまで要素を足し合わせる
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s

    def add(self, i, x):
        # i 番目のところに要素を足し合わせる
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)

    def get(self, i, j):
        # i番目からj番目までの要素の合計値を数える(1<=i<=j<=Nという制約がついているけど)
        return self.to_sum(j)-self.to_sum(i-1)

    def bisect_right(self, i):
        # i 番目から　次に初めて1増えるところまでの最大の値 j を求める
        l = i
        r = self.n
        if self.get(i, r) == r-i+1:
            return r
        while r-l > 1:
            M = (l+r)//2
            if self.get(i, M) < M-i+1:
                r = M
            else:
                l = M
        return l

    def bisect_left(self, i):
        # i 番目から最後に初めて1減るところまでの最小のjを求める
        l = 1
        r = i
        if self.get(l, i) == i+1-l:
            return l
        while r-l > 1:
            M = (r+l)//2
            if self.get(M, i) < i+1-M:
                l = M
            else:
                r = M
        return r


N = int(input())
a = list(map(int, input().split()))
b = [(a[i], i+1) for i in range(N)]
b.sort(reverse=True)
tree = BIT(N)
ans = 0

for value, index in b:
    tree.add(index, 1)

    ans += (tree.bisect_right(index)-index+1) * \
        (index-tree.bisect_left(index)+1)*value

print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)
 
input = sys.stdin.buffer.readline

class SegTree():
    # 1-indexed
    def __init__(self, N, function, basement):
        self.n = N
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def find_max_index(self, L, R, X):
        # [L,R)でX以下の物で最大indexを取得
        return self.fMi(L, R, X, 1, 0, 2**self.K)

    def find_min_index(self, L, R, X):
        # [L,R) でX以下の物で最小のindexを取得する
        return self.fmi(L, R, X, 1, 0, 2**self.K)

    def fMi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vr = self.fMi(a, b, x, (k << 1) | 1, (l + r) // 2, r)
                if vr != -1:
                    return vr
                return self.fMi(a, b, x, k << 1, l, (l + r) // 2)

    def fmi(self, a, b, x, k, l, r):
        if self.seg[k] > x or r <= a or b <= l:
            return -1
        else:
            if k >= 2**self.K:
                return k-2**self.K
            else:
                vl = self.fmi(a, b, x, k << 1, l, (l+r)//2)
                if vl != -1:
                    return vl
                return self.fmi(a, b, x, k << 1 | 1, (l+r)//2, r)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    seg = SegTree(N, min, N+1)
    B = [0]*N
    for i, v in enumerate(A):
        B[i] = (i, A[i])
    B.sort(key=lambda x: x[1])
    ans = 0
    for index, v in B:
        seg.update(index, 1)
        left = seg.find_max_index(0, index, 1)
        right = seg.find_min_index(index+1, N, 1)
        if right == -1:
            right = N
        ans += v*(index-left)*(right-index)
    print(ans)
if __name__=="__main__":
    main()