andrew-and-wengaluru-city

Andrew has recently moved to Wengaluru. He finds this city amazing as all the buildings of the city are of same shape. There are N buildings in a row with no space in between. Buildings may have different heights while width in other two dimensions is always 1 unit.   

Rain occurs very frequently in Wengaluru so Andrew being the curious boy thought that if the entire city is flooded with water then How much water would be collected between the buildings? Water would be collected between the buildings if a small sized building occurs between 2 big sized building i.e. if a building with small height occurs between buildings of relatively larger height.

Input 
The first line contains T, the number of test cases. 
Each test case consist of 2 lines. First line of each test case Would contain N- total no. of buildings in the city.
Second line contains N integers, the height of N buildings.

Output
For each test case output the answer to the above query. As the total water collected between the buildings could be a huge number so output your answer by taking Modulus with 10^9+7(1000000007).

Constraints
1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^7

SAMPLE INPUT
2
5
3 2 1 4 5
5
1 2 3 4 5

SAMPLE OUTPUT
3
0

Explanation

In the 1st testcase height of the buildings are 3,2,1,4 and 5.So for 2nd building it could collect 1 unit of water,3rd building could collect 2 units,which sums up to 3.
In the 2nd testcase as we can see no water could be collected between any 2 buildings.So total water collected would be 0 units.

Source: hackerearth | Difficulty: EASY


Solutions:
def main():
	for i in range(eval(input())):
		n = eval(input())
		A = list(map(int, input().split()))
	
		max = 0
		maxIndex = 0
		
		for i in range(0,len(A)):
			if A[i] > max:
				max = A[i]
				maxIndex = i
                
		previousMax = 0
		count = 0
		
		for i in range(0, maxIndex):
			if A[i] > previousMax:
				previousMax = A[i]
			count += previousMax - A[i]
        
		previousMax = 0
		for i in range(len(A)-1, maxIndex, -1):
			if A[i] > previousMax:
				previousMax = A[i]
			count += previousMax - A[i]
        	
        	print(count%1000000007)
        return 0
        
if __name__ == "__main__":
	main()        


m = eval(input())

for i in range(m):
	k = int(input())
	l = [int(i) for i in input().split()]
	left = [0]*len(l)
	right = [0]*len(l)
	for i in range(1,len(l)):
		left[i] = max(left[i-1], l[i-1])
	
	for i in range(len(l)-2,-1,-1):
		right[i] = max(right[i+1], l[i+1])
		
	ans = 0
	for i in range(len(l)):
		if min(left[i],right[i]) > l[i]:
			ans += min(left[i],right[i]) - l[i]
	
	print(ans%1000000007)


T = int(input())
for t in range (T):
	N = int(input())
	h = [-1]+[int(x) for x in input().split()]
	left_max = [0]*(N+1)
	right_max = [0]*(N+1)
	left_max[1],right_max[-1] = h[1],h[-1]
   
	for i in range(2,N+1):
		left_max[i] = max(left_max[i-1],h[i])
		right_max[N-i+1]= max(right_max[N-i+2],h[N-i+1])
	ans=0


	for i in range(1,N+1):
		ans+=(min(left_max[i],right_max[i])-h[i])
		
  
 


	
	print((ans)%1000000007)
			
		
	


import sys
def trap(A):
	if not A: return 0
	res, l, r = 0, [A[0]] * len(A), [A[len(A) - 1]] * len(A)
	for i in range(1, len(A)): 
		l[i], r[-i - 1] = max(A[i], l[i - 1]), max(A[-i - 1], r[-i])
	for i in range(1, len(A) - 1):
		res += max(0, (min(l[i - 1], r[i + 1]) - A[i]))
	return res%1000000007
test=eval(input())
for t in range(0,test):
	n=eval(input())
	s=list(map(int,sys.stdin.readline().split()))
	print(trap(s))


def waterfilled(arr,n):
	ans = 0
	left = [0]*(n+10)
	right = [0]*(n+10)
	left[0]=arr[0]
	for i in range(1,n):
		if arr[i]>left[i-1]:
			left[i]=arr[i]
		else:
			left[i]=left[i-1]
			
			
	right[n-1]=arr[n-1]
	for i in range(n-2,-1,-1):
		if arr[i]>right[i+1]:
			right[i] = arr[i]
		else:
			right[i] = right[i+1]
	
	for i in range(1,n-1):
		tmp = min(left[i-1],right[i+1])
		if tmp-arr[i]>0:
			ans = (ans+(tmp-arr[i]))%1000000007
	
	return ans
			
def main():
	t = eval(input())
	for i in range(t):
		n = eval(input())
		arr = list(map(int,input().split()))
		print(waterfilled(arr,n))
		
main()
			


T = int(input())
for t in range(0,T):
	N = int(input())
	lst = input()
		
	lst2=list(map(int,lst.strip().split()))
	mini = []
	maxi = []
	mini.append(lst2[0])
	for i in range(0,len(lst2)-1):
		maxi.append(0)
	maxi.append(lst2[len(lst2)-1])	
	
	for j in range(1,len(lst2)):
		if lst2[j] > mini[j-1]:
			mini.append(lst2[j])
		else:
			mini.append(mini[j-1])
	
	p = len(lst2)-2

	while p >= 0:
		if maxi[p+1] > lst2[p]:
			maxi[p]=maxi[p+1]
		else:
			maxi[p]=lst2[p]
		p = p-1
	
	water = 0
	for i in range(1,len(lst2)-1):
		if mini[i-1] < maxi[i+1]:
			if mini[i-1]-lst2[i]>=1:
				water = (water + (mini[i-1]-lst2[i]))%1000000007
		else:
			if maxi[i+1]-lst2[i]>=1:
				water = (water + (maxi[i+1]-lst2[i]))%1000000007
	
	print(water)
	
	
					
			
					
					


t=int(input())
for test in range(t):
	n=int(input())
	a=list(map(int,input().split()))
	onleft=[0]*n
	onright=[0]*n
	max_so_far=0
	
	for i in range(n):
			if(a[i]>=max_so_far):
				max_so_far=a[i]
				onleft[i]=0
			else:
				onleft[i]=max_so_far
	max_so_far=0
	for i in range(n-1,-1,-1):
			if(a[i]>=max_so_far):
				max_so_far=a[i]
				onright[i]=0
			else:
				onright[i]=max_so_far
	p_sum=0
	for i in range(n):
		if (onleft[i]!=0 and onright[i]!=0):
					p_sum+=min(onleft[i],onright[i])-a[i]
	print(p_sum%1000000007)


import sys
def trap(A):
	if not A: 
		return 0
	res=0
	l=[A[0]] * len(A)
	r=[A[len(A) - 1]] * len(A)
	
	for i in range(1, len(A)): 
		l[i]= max(A[i], l[i - 1])
		r[-i - 1] = max(A[-i - 1], r[-i])

	for i in range(1, len(A) - 1):
		res += max(0, (min(l[i - 1], r[i + 1]) - A[i]))
	
	return res%1000000007

test=eval(input())
for t in range(0,test):
	n=eval(input())
	s=list(map(int,sys.stdin.readline().split()))
	print(trap(s))


#!/usr/bin/env python
# -*- coding: utf-8 -*-

# https://www.hackerearth.com/problem/algorithm/andrew-and-wengaluru-city/

# Idea:
# - find topmost building(s)
# - in case if there're many of such buildings, all spaces between them are
#   filled with water
# - find topmost buildings to the left and to the right from it
# - repeat
#
# to find max building on a segment quickly enough, we can use Fenwick tree or
# segment tree

import math
import copy


# There can be following usecases for segment tree:
# 1. Set values and find max/min/sum on an interval


class SegmentTree:

	def __init__(self, size):
		# size of array | size of tree | depth
		# 1, 1, 1
		# 2, 3, 2
		# 3, 7, 3
		# 4, 7, 3
		# 5, 15, 4

		self.size = size
		pow_of_2 = int(math.log(size) / math.log(2))
		if pow(2, pow_of_2) != size:
			pow_of_2 += 1
		self.depth = pow_of_2 + 1
		self.pow_2_size = (1 << pow_of_2)
		self.array = [{"value": 0, "pos": []}] * (1 << self.depth)

	def __update(self, pos, value, fro, to, index, depth):
		if depth < self.depth:
			if value > self.array[index]["value"]:
				self.array[index] = {"value": value, "pos": [pos]}
			elif value == self.array[index]["value"]:
				self.array[index]["pos"].append(pos)
			index <<= 1
			mid = (fro + to) // 2
			depth += 1
			if fro <= pos < mid:
				self.__update(pos, value, fro, mid, index, depth)
			else:
				self.__update(pos, value, mid, to, index | 1, depth)

	def update(self, pos, value):
		self.__update(pos, value, 0, self.pow_2_size, 1, 0)

	def __find_max_value_and_pos(self, left, right, fro, to, index, depth):
		if left == fro and right == to:
			return self.array[index]
		else:
			index <<= 1
			mid = (fro + to) // 2
			max_value_and_pos = {"value": 0, "pos": []}
			depth += 1
			if fro <= left and right <= mid:
				max_value_and_pos = self.__find_max_value_and_pos(
					left, right, fro, mid, index, depth)
			elif mid <= left and right <= to:
				max_value_and_pos = self.__find_max_value_and_pos(
					left, right, mid, to, index | 1, depth)
			else:
				value_and_pos = self.__find_max_value_and_pos(
					left, mid, fro, mid, index, depth)
				if value_and_pos["value"] > max_value_and_pos["value"]:
					max_value_and_pos = value_and_pos
				elif (value_and_pos["value"] == max_value_and_pos["value"] and
						value_and_pos["value"] != 0):
					max_value_and_pos["pos"].extend(value_and_pos["pos"])

				value_and_pos = self.__find_max_value_and_pos(
					mid, right, mid, to, index | 1, depth)
				if value_and_pos["value"] > max_value_and_pos["value"]:
					max_value_and_pos = value_and_pos
				elif (value_and_pos["value"] == max_value_and_pos["value"] and
						value_and_pos["value"] != 0):
					max_value_and_pos["pos"].extend(value_and_pos["pos"])
			return max_value_and_pos

	def find_max_value_and_pos(self, left, right):
		return self.__find_max_value_and_pos(left, right, 0, self.pow_2_size,
											 1, 0)

	def find_bounds_and_amount_of_water(self, left, right, bound):
		add = 0
		max_value_and_pos = self.find_max_value_and_pos(left, right)
		if bound == -1:
			pos_list = max_value_and_pos["pos"]
		else:
			pos_list = copy.copy(max_value_and_pos["pos"])
			if pos_list:
				if bound < pos_list[0]:
					pos_list.insert(0, bound)
				else:
					pos_list.append(bound)
		prev_pos = -1
		for pos in pos_list:
			if prev_pos != -1:
				for i in range(prev_pos, pos):
					add += max_value_and_pos["value"] - A[i]
			prev_pos = pos + 1
		if not max_value_and_pos["pos"]:
			return (add, left, right)
		else:
			return (add, max_value_and_pos["pos"][0],
					max_value_and_pos["pos"][-1] + 1)

# class FenwickTree:
#
#     def __init__(self, size, func):
#         self.func = func
#         self.data = [0] * size
#         self.min = None
#
#     def update(self, pos, value):
#         assert pos < len(self.data)
#         if None == self.min:
#             self.min = value
#         else:
#             self.min = min(self.min, value)
#         while pos < len(self.data):
#             self.data[pos] = self.func(self.data[pos], value)
#             pos |= pos + 1
#
#     def lookup(self, pos):
#         assert pos < len(self.data)
#         result = self.min
#         while pos >= 0:
#             result = self.func(self.data[pos], result)
#             pos &= pos + 1
#             pos -= 1
#         return result

T = int(input())
for t in range(0, T):
	N = int(input())
	A = [int(x) for x in input().split()]

	segment_tree = SegmentTree(N)
	for i in range(0, N):
		segment_tree.update(i, A[i])

	total = 0
	add, left, right = segment_tree.find_bounds_and_amount_of_water(0, N, -1)
	total += add

	while left != 0:
		was_left = left
		add, left, _ = segment_tree.find_bounds_and_amount_of_water(
			0, left, left)
		total += add
	while right != N:
		was_right = right
		add, _, right = segment_tree.find_bounds_and_amount_of_water(
			right, N, right - 1)
		total += add

	print(total % 1000000007)

# ft_left = FenwickTree(len(A), lambda x, y: x.value > y.value and x or y)
# ft_right = FenwickTree(len(A), lambda x, y: x.value > y.value and x or y)
# for i in xrange(0, len(A)):
#     ft_left.update(i, {'value': A[len(A) - 1 - i], 'index': len(A) - 1 - i})
#
# topmost_left = ft_left.lookup(N - 1)
# topmost_right = topmost_left
#
# total_sum = 0
# while topmost_left.index != 0:
#     next_topmost_left = ft_left.lookup(topmost_left - 1)
#     for i in xrange(topmost_left.index, next_topmost_left.index):
#         total_sum += A[i] - next_topmost_left.value
#     topmost_left = next_topmost_left
#
# while topmost_right.index != len(A) - 1:
#     next_topmost_right = ft_right.lookup(topmost_right + 1)
#     for i in xrange(topmost_right.index + 1, next_topmost_right.index):
#         total_sum += A[i] - next_topmost_right.value
#     topmost_right = next_topmost_right


cases = int(input())

def sumWater(lst, stop):
	currentLeft = 0
	currentMaxRight = 0
	currentAcc = []
	total = 0
	for x in lst:
		
		if x > currentLeft:
			if len(currentAcc) > 0:
				for r in currentAcc:
					total += (currentLeft-r)
				currentAcc = []
			currentLeft = x
		elif x < currentLeft:
			currentAcc.append(x)
		else:
			if len(currentAcc) > 0:
				for r in currentAcc:
					total += (currentLeft-r)
				currentAcc = []
		if x == stop:
			for r in currentAcc:
				total += (currentLeft-r)
			return total
	return total

for n in range(cases):
	num = int(input())
	lst = list(map(int,input().split()))
	
	currentLeft = 0
	currentMaxRight = 0
	currentAcc = []
	total = 0
	for x in lst:
		if x > currentLeft:
			if len(currentAcc) > 0:
				for r in currentAcc:
					total += (currentLeft-r)
				currentAcc = []
			currentLeft = x
		elif x < currentLeft:
			currentAcc.append(x)
		else:
			if len(currentAcc) > 0:
				for r in currentAcc:
					total += (currentLeft-r)
				currentAcc = []
	
	if len(currentAcc) > 0:
		total += sumWater(lst[::-1],currentLeft)
	
	print(total%1000000007)


left = [0]*(10**5+10)
right = [0]*(10**5+10)
def waterfilled(arr,n):
	ans = 0
	
	left[0]=arr[0]
	for i in range(1,n):
		if arr[i]>left[i-1]:
			left[i]=arr[i]
		else:
			left[i]=left[i-1]
			
			
	right[n-1]=arr[n-1]
	for i in range(n-2,-1,-1):
		if arr[i]>right[i+1]:
			right[i] = arr[i]
		else:
			right[i] = right[i+1]
	
	for i in range(1,n-1):
		tmp = min(left[i-1],right[i+1])
		if tmp-arr[i]>0:
			ans = (ans+(tmp-arr[i]))%1000000007
	
	return ans
			
def main():
	t = eval(input())
	for i in range(t):
		n = eval(input())
		arr = list(map(int,input().split()))
		print(waterfilled(arr,n))
		
main()