Untitled
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)