Untitled

mail@pastecode.io avatar
unknown
python
a year ago
871 B
3
Indexable
Never
# Example test:
# 1
# 4
# 1 3 1 7

def Find(arr, n):
    s_left = [0] * n
    s_right = [0] * n
    q = []
    for i in range(0, n):
        while (len(q) != 0 and
               arr[q[-1]] <= arr[i]):
            s_left[i] += s_left[q[-1]] + 1
            q.pop()        
        q.append(i)
    while len(q) != 0:
        q.pop()
    for i in range(n - 1, -1, -1):
        while (len(q) != 0 and
               arr[q[-1]] < arr[i]):
            s_right[i] += s_right[q[-1]] + 1
            q.pop()
        q.append(i)
    while len(q) != 0:
        q.pop()
    ans = 0
    for i in range(0, n):
        ans += (s_left[i] + 1) * (s_right[i] + 1) * arr[i]
    return ans

if __name__ == "__main__":
    t = int(input())
    while t != 0:
        t -= 1
        n = int(input())
        arr = [int(i) for i in input().split()]
        res = Find(arr, n)
        print(res)