In a fictitious city of CODASLAM there were many skyscrapers. The mayor of the city decided to make the city beautiful and for this he decided to arrange the skyscrapers in descending order of their height, and the order must be strictly decreasing but he also didn’t want to waste much money so he decided to get the minimum cuts possible. Your job is to output the minimum value of cut that is possible to arrange the skyscrapers in descending order.

-----Input-----

*First line of input is the number of sky-scrappers in the city
*Second line of input is the height of the respective sky-scrappers


-----Output-----

* Your output should be the minimum value of cut required to arrange these sky-scrappers in descending order.

-----Example-----
Input:
5
1 2 3 4 5

Output:
8

By:
Chintan,Asad,Ashayam,Akanksha

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import sys
num = int(sys.stdin.readline())
s = sys.stdin.readline().split()
sky = list(map(int, s))
sky.reverse()
cuts = 0
change = 0
t = False
i = 1
while i < len(sky):
	if sky[i] <= sky[i - 1]:
		for j in range(i - 1, -1, -1):
			if sky[j] <= sky[i] - (i - j):
				break
			else:
				change += sky[j] - (sky[i] - (i - j))
			if change >= sky[i]:
				change = sky[i]
				t = True
				break
		cuts += change
		if t:
			del sky[i]
			t = False
			i -= 1
		else:
			for j in range(i - 1, -1, -1):
				if sky[j] < sky[i] - (i - j):
					break
				else:
					sky[j] = sky[i] - (i - j)
	i += 1
	change = 0
print(cuts)


def main():
	N = int(input())
	while True:
		try:
			X = input()
		except:
			break
		H = list(map(int, X.split()))
		C = 0
		while H:
			e = H.pop(0)
			(H2, C1, C2) = (list(H), e, 0)
			for i in range(len(H2)):
				if H2[i] > e - 1:
					C2 += H2[i] - (e - 1)
					H2[i] = e - 1
			if C1 <= C2:
				C += C1
			else:
				C += C2
				H = H2
		print(C)
main()