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

Difficulty: interview

Starter code:

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)

#!/usr/bin/env python

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
   #print C+C2, H2, C+C1, H
   if C1 <= C2:
    C += C1
   else:
    C += C2
    H = H2
  print(C)

main()



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)