Gotham has been attacked by Joker . Bruce Wayne has deployed an automatic machine gun at each tower of Gotham.
All the towers in Gotham are in a straight line.
You are given no of towers 'n' followed by the height of 'n' towers.
For every tower(p), find the height of the closest tower (towards the right), greater than the height of the tower(p).
Now, the Print sum of all such heights (mod 1000000001).
Note: If for a tower(k), no such tower exists then take its height as 0.
Example 1:
Ã¢â¬â¹Input : arr[]= {112, 133, 161, 311, 122, 
                    512, 1212, 0, 19212}
Output : 41265
Explanation:
nextgreater(112) : 133
nextgreater(133) : 161
nextgreater(161) : 311
nextgreater(311) : 512
nextgreater(122) : 512
nextgreater(512) : 1212
nextgreater(1212) : 19212
nextgreater(0) : 19212
nextgreater(19212) : 0
add = 133+161+311+512+512+1212+19212+19212+0 
add = 41265.
Ã¢â¬â¹Example 2:
Input : arr[] = {5, 9, 7, 6} 
Output :  9
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function save_gotham() that takes an array (arr), sizeOfArray (n), and return the sum of next greater element of every element. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ A[i] ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3



def save_gotham (arr, n) : 

    #Complete the function

    



Solutions:
def save_gotham(arr, n):
	stack = [arr[n - 1]]
	ns = [0]
	for i in range(n - 2, -1, -1):
		if arr[i] < stack[-1]:
			ns.append(stack[-1])
		else:
			while len(stack) > 0 and stack[-1] <= arr[i]:
				stack.pop()
			if len(stack) == 0:
				ns.append(0)
			else:
				ns.append(stack[-1])
		stack.append(arr[i])
	return sum(ns) % 1000000001


def save_gotham(arr, n):
	stack = []
	sum1 = 0
	for i in range(n):
		if stack == []:
			stack.append(arr[i])
		else:
			while stack:
				if stack[-1] < arr[i]:
					sum1 += arr[i]
					stack.pop()
				else:
					break
			stack.append(arr[i])
	return sum1


def save_gotham(arr, n):
	s = []
	l = []
	for i in range(n - 1, -1, -1):
		if s and s[-1] > arr[i]:
			l.append(s[-1])
		elif s and s[-1] <= arr[i]:
			while s and s[-1] <= arr[i]:
				s.pop()
			if not s:
				l.append(0)
			else:
				l.append(s[-1])
		s.append(arr[i])
	return sum(l) % 1000000001


def save_gotham(arr, n):
	MOD = 10 ** 9 + 1
	ans = 0
	stk = []
	for v in reversed(arr):
		while stk and v >= stk[-1]:
			stk.pop()
		ans = (ans + (stk[-1] if stk else 0)) % MOD
		stk.append(v)
	return ans


def save_gotham(arr, n):
	stack = []
	ans = 0
	i = n - 2
	stack.append(arr[-1])
	mod = 1000000001
	while i >= 0:
		if stack[-1] <= arr[i]:
			while len(stack) > 0 and stack[-1] <= arr[i]:
				stack.pop()
			if len(stack) == 0:
				ans += 0
				stack.append(arr[i])
			else:
				ans = (ans % mod + stack[-1]) % mod
				stack.append(arr[i])
		else:
			ans = (ans % mod + stack[-1]) % mod
			stack.append(arr[i])
		i -= 1
	return ans


def save_gotham(arr, n):
	MOD = 1000000001
	stack = []
	ans = 0
	for x in arr:
		while stack and stack[-1] < x:
			ans = (ans + x) % MOD
			stack.pop()
		stack.append(x)
	return ans


def save_gotham(arr, n):
	stk = []
	total = 0
	for i in range(n - 1, -1, -1):
		while stk and stk[-1] <= arr[i]:
			stk.pop()
		if stk:
			total = (total + stk[-1]) % 1000000001
		stk.append(arr[i])
	return total


def save_gotham(arr, n):
	s = []
	ans = []
	for j in range(n - 1, -1, -1):
		while len(s) > 0 and s[-1] <= arr[j]:
			s.pop()
		if len(s) == 0:
			ans.append(0)
		else:
			ans.append(s[-1])
		s.append(arr[j])
	return sum(ans) % 1000000001


def save_gotham(arr, n):
	res = [0] * n
	st = []
	s = 0
	for i in range(n - 1, -1, -1):
		while st and st[-1] <= arr[i]:
			st.pop()
		if st:
			res[i] = st[-1]
			s += res[i]
		st.append(arr[i])
	return s


def save_gotham(arr, n):
	s = 0
	t = [0]
	for i in range(1, n):
		while len(t) > 1 and arr[i] > arr[t[-1]]:
			s += arr[i]
			t.pop()
		if len(t) == 1 and arr[i] > arr[t[-1]]:
			s += arr[i]
			t.pop()
		t.append(i)
	return s


def save_gotham(arr, n):
	op = []
	st = []
	for i in range(n - 1, -1, -1):
		while len(st) > 0 and st[-1] <= arr[i]:
			st.pop()
		if len(st) == 0:
			op.append(0)
			st.append(arr[i])
		else:
			op.append(st[-1])
			st.append(arr[i])
	return sum(op)


def save_gotham(arr, n):
	stack = []
	opt = [0] * n
	i = 0
	while i < n:
		if not stack:
			stack.append(i)
		elif arr[stack[-1]] >= arr[i]:
			stack.append(i)
		while stack and arr[stack[-1]] < arr[i]:
			a = stack.pop()
			opt[a] = arr[i]
			i -= 1
		i += 1
	return sum(opt)


def save_gotham(arr, n):
	st = []
	res = []
	arr = arr[::-1]
	for i in arr:
		if not st:
			res.append(-1)
			st.append(i)
		else:
			while st and i >= st[-1]:
				st.pop()
			if st:
				res.append(st[-1])
				st.append(i)
			else:
				res.append(-1)
				st.append(i)
	res = res[::-1]
	s = 0
	for ele in res:
		if ele > 0:
			s += ele
	return s


def save_gotham(arr, n):
	summa = 0
	stack = []
	for item in arr:
		while stack and stack[-1] < item:
			summa += item
			stack.pop()
		stack.append(item)
	return summa


def save_gotham(arr, n):
	result = 0
	stack = []
	for item in arr[::-1]:
		while stack and stack[-1] <= item:
			stack.pop()
		if stack:
			result += stack[-1]
		stack.append(item)
	return result


def save_gotham(arr, n):
	l = []
	st = []
	i = n - 1
	while i >= 0:
		if len(st) == 0:
			l.append(0)
			st.append(arr[i])
			i -= 1
		elif st[-1] > arr[i]:
			l.append(st[-1])
			st.append(arr[i])
			i -= 1
		else:
			while st and st[-1] <= arr[i]:
				st.pop(-1)
	try:
		return sum(l)
	except:
		return 0


def save_gotham(arr, n):
	stck = []
	lis = []
	summ = 0
	i = len(arr) - 1
	while i > -1:
		if len(stck) == 0:
			stck.append(arr[i])
			lis.append(0)
			i -= 1
		elif stck[-1] > arr[i]:
			lis.append(stck[-1])
			stck.append(arr[i])
			i -= 1
		else:
			stck.pop()
	for k in lis[::-1]:
		summ += k
	return summ % 1000000001


def save_gotham(arr, n):
	stack = []
	b = 0
	i = n - 1
	while i >= 0:
		if len(stack) != 0:
			if stack[-1] > arr[i]:
				b = b + stack[-1]
				stack.append(arr[i])
				i = i - 1
			else:
				stack.pop()
		else:
			stack.append(arr[i])
			b = b + 0
			i = i - 1
	return b


def save_gotham(arr, n):
	stack = []
	sum = 0
	for i in range(n - 1, -1, -1):
		while stack and arr[i] >= stack[-1]:
			stack.pop()
		if stack:
			sum += stack[-1]
		stack.append(arr[i])
	return sum


def save_gotham(arr, n):
	stack = [0]
	res = 0
	for i in range(1, n):
		if len(stack) == 0 or arr[stack[-1]] >= arr[i]:
			stack.append(i)
		else:
			while stack and arr[stack[-1]] < arr[i]:
				res = (res + arr[i]) % 1000000001
				stack.pop()
			stack.append(i)
	return res


def save_gotham(arr, n):
	stack = []
	result = []
	for i in range(n - 1, -1, -1):
		if len(stack) == 0:
			result.append(0)
		elif len(stack) > 0 and stack[-1] > arr[i]:
			result.append(stack[-1])
		elif len(stack) > 0 and stack[-1] <= arr[i]:
			while len(stack) > 0 and stack[-1] <= arr[i]:
				stack.pop()
			if len(stack) == 0:
				result.append(0)
			else:
				result.append(stack[-1])
		stack.append(arr[i])
	return sum(result)


def save_gotham(arr, n):
	stack = [arr[0]]
	total = 0
	for i in range(1, n):
		if not stack:
			stack.append(arr[i])
		else:
			while stack and stack[-1] < arr[i]:
				total += arr[i]
				stack.pop()
			stack.append(arr[i])
	return total


def save_gotham(arr, n):
	stk = []
	lis = []
	i = n - 1
	while i > -1:
		if len(stk) == 0:
			stk.append(arr[i])
			lis.append(0)
			i -= 1
		elif stk[-1] > arr[i]:
			lis.append(stk[-1])
			stk.append(arr[i])
			i -= 1
		else:
			stk.pop()
	return sum(lis) % 1000000001


from collections import deque

def save_gotham(a, n):
	s = deque()
	o = []
	for i in range(n - 1, -1, -1):
		while s and a[s[-1]] <= a[i]:
			s.pop()
		if s:
			o.append(a[s[-1]])
		else:
			o.append(0)
		s.append(i)
	o.reverse()
	return sum(o)


def save_gotham(arr, n):
	stack = []
	stack.append(1000000000)
	ans = [0] * n
	for i in range(n):
		j = n - i - 1
		if stack[-1] == 1000000000:
			ans[j] = 0
			stack.append(arr[j])
		elif stack[-1] > arr[j]:
			ans[j] = stack[-1]
			stack.append(arr[j])
		else:
			while stack[-1] != 1000000000 and stack[-1] <= arr[j]:
				stack.pop()
			if stack[-1] != 1000000000:
				ans[j] = stack[-1]
			stack.append(arr[j])
	return sum(ans) % 1000000001


from bisect import bisect_right

def save_gotham(arr, n):
	b = [0] * n
	s = [arr[n - 1]]
	for i in range(n - 2, -1, -1):
		while len(s) != 0 and arr[i] >= s[-1]:
			s.pop()
		if len(s) != 0:
			b[i] = s[-1]
		s.append(arr[i])
	s = 0
	for i in b:
		s += i
		s = s % 1000000007
	return s


def save_gotham(A, n):
	S = [A[0]]
	x = 0
	for i in range(1, len(A)):
		while A[i] > S[-1]:
			x += A[i]
			S.pop()
			if len(S) == 0:
				break
		S.append(A[i])
	return x


def save_gotham(arr, n):
	s = 0
	stack = []
	nxt = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		while len(stack) > 0 and arr[i] >= stack[-1]:
			stack.pop()
		nxt[i] = 0 if len(stack) == 0 else stack[-1]
		stack.append(arr[i])
	for x in nxt:
		s += x % 1000000001
	return s


def save_gotham(arr, n):
	es = []
	st = []
	for i in range(len(arr) - 1, -1, -1):
		if len(st) == 0:
			es.insert(0, 0)
		elif st[-1] > arr[i]:
			es.insert(0, st[-1])
		elif st[-1] <= arr[i]:
			while len(st) > 0 and st[-1] <= arr[i]:
				st.pop()
			if len(st) == 0:
				es.insert(0, 0)
			else:
				es.insert(0, st[-1])
		st.append(arr[i])
	return sum(es)


def NGR(arr, n, res=[]):
	stack = []
	for i in range(n - 1, -1, -1):
		if len(stack) == 0:
			res.append(0)
		elif len(stack) > 0 and arr[i] < stack[-1]:
			res.append(stack[-1])
		elif len(stack) > 0 and arr[i] >= stack[-1]:
			while len(stack) > 0 and arr[i] >= stack[-1]:
				stack.pop()
			if len(stack) == 0:
				res.append(0)
			else:
				res.append(stack[-1])
		stack.append(arr[i])
	return res[::-1]

def save_gotham(arr, n):
	a = arr
	stack = []
	ans = [0 for i in range(n)]
	res = 0
	for i in range(n - 1, -1, -1):
		while len(stack) > 0 and a[i] >= stack[-1]:
			stack.pop()
		ans[i] = 0 if len(stack) == 0 else stack[-1]
		stack.append(a[i])
	for x in ans:
		res += x % 1000000001
	return res


def save_gotham(arr, n):
	l = [0 for i in range(n)]
	s = []

	def top():
		return s[-1]

	def push(x):
		s.append(x)

	def pop():
		t = s[-1]
		del s[-1]
		return t
	s.append(0)
	for i in range(1, n):
		if arr[i] < arr[top()]:
			push(i)
		else:
			while len(s) > 0 and arr[top()] < arr[i]:
				k = pop()
				l[k] = arr[i]
			push(i)
	while len(s) > 0:
		t = pop()
		l[t] = 0
	return sum(l)
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = save_gotham(arr, n)
	print(ans)


def save_gotham(arr, n):
	ans = []
	x = []
	ans.append(0)
	x.append(arr[-1])
	arr = arr[::-1]
	for i in arr[1:]:
		while len(x) > 0 and i >= x[-1]:
			x.pop()
		if len(x) == 0:
			ans.append(0)
		else:
			ans.append(x[-1])
		x.append(i)
	return sum(ans)
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = save_gotham(arr, n)
	print(ans)


def save_gotham(arr, n):
	mod = 1000000001
	stack = []
	Sum = 0
	for i in range(n - 1, -1, -1):
		while len(stack) != 0 and arr[i] >= stack[-1]:
			stack.pop()
		if len(stack) == 0:
			Sum = Sum + 0
		else:
			Sum = Sum + stack[-1]
		stack.append(arr[i])
	return Sum
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = save_gotham(arr, n)
	print(ans)


def save_gotham(arr, n):
	stack = []
	ans = [0] * n
	ans[n - 1] = 0
	stack.append(0)
	for i in range(1, n):
		while stack and arr[stack[-1]] < arr[i]:
			ans[stack[-1]] = arr[i]
			stack.pop()
		stack.append(i)
	return sum(ans) % 1000000001
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = save_gotham(arr, n)
	print(ans)


def save_gotham(arr, n):
	s = [arr[-1]]
	sum = 0
	for i in range(n - 2, -1, -1):
		while s[-1] <= arr[i]:
			s.pop()
			if s == []:
				break
		if s != []:
			sum += s[-1]
		s.append(arr[i])
	return sum
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = save_gotham(arr, n)
	print(ans)


def save_gotham(arr, n):
	st = []
	ans = [-1 for i in range(n)]
	st.append(0)
	for i in range(n):
		if arr[st[-1]] < arr[i]:
			while len(st) > 0 and arr[st[-1]] < arr[i]:
				ans[st[-1]] = arr[i]
				st.pop()
		st.append(i)
	sum1 = 0
	for i in range(n):
		if ans[i] != -1:
			sum1 += ans[i] % (10 ** 9 + 7)
	return sum1
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = save_gotham(arr, n)
	print(ans)


def save_gotham(arr, n):
	s = []
	res = [0] * n
	for i in range(n - 1, -1, -1):
		if len(s) > 0:
			while len(s) > 0 and s[-1] <= arr[i]:
				s.pop()
		if len(s) != 0:
			res[i] = s[-1]
		s.append(arr[i])
	return sum(res) % 1000000001
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ans = save_gotham(arr, n)
	print(ans)


def save_gotham(arr, n):
	stack = []
	res = []
	for i in reversed(arr):
		while len(stack) != 0 and stack[-1] <= i:
			stack.pop()
		if len(stack) == 0:
			res.append(0)
		else:
			res.append(stack[-1])
		stack.append(i)
	return sum(res)


def save_gotham(arr, n):
	a = [0] * n
	s = [0]
	for i in range(1, n):
		if arr[s[-1]] >= arr[i]:
			s.append(i)
		else:
			while arr[s[-1]] < arr[i]:
				d = s.pop()
				a[d] = arr[i]
				if len(s) == 0:
					break
			s.append(i)
	return sum(a) % 1000000001


def save_gotham(arr, n):
	s = []
	res = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		if len(s) != 0:
			while len(s) != 0 and s[-1] <= arr[i]:
				s.pop()
		res[i] = 0 if len(s) == 0 else s[-1]
		s.append(arr[i])
	return sum(res)


mod = 1000000001

def save_gotham(arr, n):
	sum = 0
	a = []
	for j in range(-1, -n - 1, -1):
		while len(a) != 0 and arr[j] >= a[len(a) - 1]:
			a.pop()
		if len(a) == 0:
			sum += 0
		else:
			sum += a[len(a) - 1]
		a.append(arr[j])
	return sum % mod


def save_gotham(a, n):
	st = []
	ans = [0 for i in range(n)]
	res = 0
	for i in range(n - 1, -1, -1):
		while len(st) > 0 and a[i] >= st[-1]:
			st.pop()
		ans[i] = 0 if len(st) == 0 else st[-1]
		st.append(a[i])
	for x in ans:
		res += x % 1000000001
	return res


def save_gotham(arr, n):
	s = []
	c = 0
	for i in range(n - 1, -1, -1):
		while s and s[-1] <= arr[i]:
			s.pop()
		if len(s) == 0:
			c = c + 0
		else:
			c = c + s[-1]
		s.append(arr[i])
	return c % 1000000001


def save_gotham(arr, n):
	st = []
	ans = [None] * n
	sum = 0
	for i in range(n - 1, -1, -1):
		while len(st) != 0 and st[len(st) - 1] <= arr[i]:
			st.pop()
		if len(st) == 0:
			ans[i] = 0
			st.append(arr[i])
		else:
			ans[i] = st[len(st) - 1]
			st.append(arr[i])
	for el in ans:
		sum += el
	return sum


def save_gotham(arr, n):
	stk = []
	result = []
	for i in range(len(arr) - 1, -1, -1):
		if not stk:
			result.append(0)
		elif stk[-1] > arr[i]:
			result.append(stk[-1])
		elif stk[-1] <= arr[i]:
			while stk and stk[-1] <= arr[i]:
				stk.pop()
			if not stk:
				result.append(0)
			else:
				result.append(stk[-1])
		stk.append(arr[i])
	return sum(result) % 1000000001


def save_gotham(a, n):
	stk = []
	res = []
	for i in range(n - 1, -1, -1):
		while len(stk) != 0 and a[i] >= stk[-1]:
			stk.pop()
		if len(stk) == 0:
			res.append(0)
		else:
			res.append(stk[-1])
		stk.append(a[i])
	return sum(res)


def save_gotham(arr, n):
	nge = [0 for i in range(n)]
	stack = [arr[n - 1]]
	sl = 1
	for i in range(n - 2, -1, -1):
		v = arr[i]
		while sl > 0 and stack[sl - 1] <= v:
			stack.pop()
			sl -= 1
		if sl != 0:
			nge[i] = stack[sl - 1]
		stack.append(v)
		sl += 1
	ans = 0
	for i in nge:
		ans += i
	ans = ans % (10 ** 9 + 1)
	return ans


def save_gotham(arr, n):
	st = [arr[0]]
	ans = 0
	for i in arr[1:]:
		while st and i > st[-1]:
			st.pop()
			ans += i
		st.append(i)
	return ans


def save_gotham(arr, n):
	stack = []
	tower_sum = 0
	mod = 1000000001
	for i in range(n - 1, -1, -1):
		while stack and stack[-1] <= arr[i]:
			stack.pop()
		if stack:
			tower_sum += stack[-1]
		stack.append(arr[i])
	return tower_sum


def save_gotham(arr, n):
	tower = list()
	max_tower = list()
	max_tower = [0] * n
	for i in range(n):
		while tower and arr[i] > arr[tower[-1]]:
			max_tower[tower[-1]] = arr[i]
			tower.pop()
		tower.append(i)
	sums = 0
	for s in max_tower:
		sums = sums + s
	return sums


def save_gotham(arr, n):
	res = [0]
	st = []
	i = n - 1
	while i >= 0:
		if len(st) == 0:
			st.append(arr[i])
			i -= 1
		elif arr[i] < st[-1]:
			res.append(st[-1])
			st.append(arr[i])
			i -= 1
		else:
			st.pop()
	return sum(res)


def save_gotham(arr, n):
	_sum = 0
	stack = []
	for i in range(n):
		while stack and stack[-1] < arr[i]:
			_sum += arr[i]
			stack.pop()
		stack.append(arr[i])
	return _sum


def save_gotham(arr, n):
	res = 0
	st = []
	for i in range(n - 1, -1, -1):
		if len(st) == 0:
			st.append(arr[i])
		elif arr[i] >= st[-1]:
			while arr[i] >= st[-1]:
				st.pop()
				if len(st) == 0:
					st.append(arr[i])
					break
			else:
				res += st[-1]
				st.append(arr[i])
		else:
			res += st[-1]
			st.append(arr[i])
	return res


def save_gotham(arr, n):
	stack = []
	tower_sum = 0
	for (indx, val) in enumerate(arr):
		while stack and val > stack[-1]:
			stack.pop()
			tower_sum += val
		stack.append(val)
	return tower_sum % 1000000001


def save_gotham(arr, n):
	m = []
	x = max(arr)
	a = []
	for i in range(n - 1, -1, -1):
		c = 0
		if i == n - 1:
			a.append(0)
			m.append(arr[i])
			continue
		if arr[i] >= m[-1]:
			while arr[i] >= m[-1]:
				m.pop()
				if len(m) == 0:
					m.append(arr[i])
					a.append(0)
					c = 1
					break
		if c == 0:
			a.append(m[-1])
			m.append(arr[i])
	return sum(a) % 1000000001


from collections import deque

def save_gotham(arr, n):
	stack = deque()
	s = 0
	stack.append(arr[-1])
	for i in range(n - 1, -1, -1):
		while len(stack) != 0 and arr[i] >= stack[-1]:
			stack.pop()
		if len(stack) != 0:
			s += stack[-1]
		stack.append(arr[i])
	return s


def save_gotham(arr, n):
	ans = [0] * n
	q = []
	for i in range(n - 1, -1, -1):
		if len(q) > 0:
			while len(q) > 0 and arr[i] >= q[-1]:
				q.pop()
		ans[i] = 0 if len(q) == 0 else q[-1]
		q.append(arr[i])
	return sum(ans) % (pow(10, 9) + 1)


def save_gotham(arr, n):
	stack = []
	res = 0
	for i in range(n - 1, -1, -1):
		curr = arr[i]
		while stack and stack[-1] <= curr:
			stack.pop()
		if stack:
			res += stack[-1]
		stack.append(curr)
	return res % 1000000001


def save_gotham(li, n):
	stack = []
	res = {}
	for i in range(len(li)):
		while not len(stack) == 0 and li[i] > li[stack[-1]]:
			res[stack[-1]] = li[i]
			stack.pop()
		stack.append(i)
	while not len(stack) == 0:
		res[stack[-1]] = 0
		stack.pop()
	return sum(res.values())


def save_gotham(arr, n):
	s = 0
	l = []
	for i in range(-1, -n - 1, -1):
		if len(l) == 0:
			s += 0
		elif l[-1] > arr[i]:
			s = s + l[-1]
		else:
			while len(l) > 0 and l[-1] <= arr[i]:
				l.pop()
			if len(l) == 0:
				s += 0
			else:
				s = s + l[-1]
		l.append(arr[i])
	return s


def save_gotham(arr, n):
	stack = []
	add = 0
	for i in arr:
		if stack:
			if stack[-1] >= i:
				stack.append(i)
			else:
				while stack and stack[-1] < i:
					add += i
					stack.pop()
				stack.append(i)
		else:
			stack.append(i)
	return add % 1000000001


def save_gotham(arr, n):
	ls = []
	sum1 = 0
	ls.append(arr[-1])
	for i in range(n - 2, -1, -1):
		p = arr[i]
		while len(ls) != 0 and p >= ls[-1]:
			ls.pop()
		if len(ls) != 0:
			sum1 += ls[-1]
		ls.append(p)
	return sum1


def save_gotham(arr, n):
	stk = []
	ans = 0
	for i in arr:
		while stk and stk[-1] < i:
			ans += i
			stk.pop()
		stk.append(i)
	return ans % 1000000001


def save_gotham(arr, n):
	st = []
	ans = 0
	for i in range(n - 1, -1, -1):
		while len(st) > 0 and st[-1] <= arr[i]:
			st.pop()
		if len(st) == 0:
			ans += 0
		else:
			ans += st[-1] % 1000000001
		st.append(arr[i])
	return ans


def save_gotham(arr, n):
	stack = []
	stack.append(arr[n - 1])
	sum = 0
	for i in range(n - 2, -1, -1):
		while stack and arr[i] >= stack[0]:
			stack.pop(0)
		else:
			if stack:
				sum += stack[0]
		stack.insert(0, arr[i])
	return sum % (10 ** 9 + 1)


def save_gotham(a, n):
	stack = []
	ans = [0] * n
	stack.append
	for i in range(n):
		if len(stack) == 0:
			stack.append(i)
			continue
		while len(stack) != 0 and a[stack[-1]] < a[i]:
			rem = stack.pop(-1)
			ans[rem] = a[i]
		stack.append(i)
	return sum(ans)


def save_gotham(arr, n):
	res = [0 for _ in range(n)]
	greaters = []
	for i in range(len(arr) - 1, -1, -1):
		while greaters and arr[greaters[-1]] <= arr[i]:
			greaters.pop()
		if greaters:
			res[i] = arr[greaters[-1]]
		greaters.append(i)
	return sum(res) % 1000000001


def save_gotham(arr, n):
	l = [arr[0]]
	ln = 1
	s = 0
	for x in range(1, n):
		while ln and l[-1] < arr[x]:
			s = (s + arr[x]) % (10 ** 9 + 10)
			l.pop()
			ln -= 1
		l.append(arr[x])
		ln += 1
	return s


def save_gotham(arr, n):
	result = 0
	stack = []
	for num in arr:
		if not stack:
			stack.append(num)
		elif stack[-1] > num:
			stack.append(num)
		else:
			while stack and stack[-1] < num:
				result += num
				stack.pop()
			stack.append(num)
	return result % 1000000001


def save_gotham(arr, n):
	x = []
	m = arr.copy()
	arr.sort(reverse=True)
	if m == arr:
		for i in range(n):
			x.append(0)
		return sum(x)
	else:
		i = 0
		j = i + 1
		b = []
		while j <= n - 1:
			if m[i] < m[j]:
				b.append(m[j])
				i = i + 1
				if i == n - 1:
					j = i
				else:
					j = i + 1
			elif j == n - 1:
				c = 0
				b.append(c)
				i = i + 1
				if i == n - 1:
					j = i
				else:
					j = i + 1
			else:
				j = j + 1
		return sum(b)


def save_gotham(arr, n):
	st = []
	right = [0] * n
	for i in range(n):
		x = arr[i]
		while st and arr[st[-1]] < x:
			right[st[-1]] = x
			st.pop()
		st.append(i)
	res = 0
	for i in range(n):
		res += right[i]
		res %= 10 ** 9 + 1
	return res