Buggy python submission (verdict: Runtime Error):
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()
A_cum = [0] * n
for i in range(n):
    if i == 0:
        A_cum[0] = A_list[0]
    else:
        A_cum[i] = A_cum[i-1] + A_list[i]

def findinfindex(sortedlist, key, l, r):
    if r - l <= 0:
        return l
    m = (l+r+1)//2
    if sortedlist[m] > key:
        return findinfindex(sortedlist, key, l, m-1)
    else:
        return findinfindex(sortedlist, key, m, r)

sadmin = -1
for b in range(A_list[n//2],A_list[(n+1)//2]+1):
    lastminus = findinfindex(A_list, b, 0, n-1)
    sadness = (2*lastminus - n + 2)*b - 2*A_cum[lastminus] + A_cum[n-1]
    if sadmin == -1:
        sadmin = sadness
    elif sadness < sadmin:
        sadmin = sadness
    else:
        break
print(sadmin)


Fixed submission:
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()

def sadness(a, mid):
    sad = 0
    for i in range(mid):
        sad += a[mid] - a[i]
    for i in range(mid+1,len(a)):
        sad += a[i] - a[mid]
    return sad

if n % 2 != 0:
    print(sadness(A_list, n//2))
else:
    print(min(sadness(A_list, n//2), sadness(A_list, n//2+1)))

Buggy python submission (verdict: Runtime Error):
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()
A_cum = [0] * n
for i in range(n):
    if i == 0:
        A_cum[0] = A_list[0]
    else:
        A_cum[i] = A_cum[i-1] + A_list[i]
def findinfindex(sortedlist, key, l, r):
    if r - l <= 0:
        return l
    m = (l+r+1)//2
    if sortedlist[m] > key:
        return findinfindex(sortedlist, key, l, m-1)
    else:
        return findinfindex(sortedlist, key, m, r)
sadmin = -1
for b in range(A_list[n//2],A_list[(n+1)//2]+1):
    lastminus = findinfindex(A_list, b, 0, n-1)
    sadness = (2*lastminus - n + 2)*b - 2*A_cum[lastminus] + A_cum[n-1]
    if sadmin == -1:
        sadmin = sadness
    elif sadness < sadmin:
        sadmin = sadness
    else:
        break
print(sadmin)


Fixed submission:
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()

def sadness(a, mid):
    sad = 0
    for i in range(mid):
        sad += a[mid] - a[i]
    for i in range(mid+1,len(a)):
        sad += a[i] - a[mid]
    return sad

if n % 2 != 0:
    print(sadness(A_list, n//2))
else:
    print(min(sadness(A_list, n//2), sadness(A_list, n//2+1)))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()
A_cum = [0] * n
for i in range(n):
    if i == 0:
        A_cum[0] = A_list[0]
    else:
        A_cum[i] = A_cum[i-1] + A_list[i]
def findinfindex(sortedlist, key, l, r):
    if r - l <= 0:
        return l
    m = (l+r+1)//2
    if sortedlist[m] > key:
        return findinfindex(sortedlist, key, l, m-1)
    else:
        return findinfindex(sortedlist, key, m, r)
sadmin = -1
for b in range(A_list[0],A_list[n-1]+1):
    lastminus = findinfindex(A_list, b, 0, n-1)
    sadness = (2*lastminus - n + 2)*b - 2*A_cum[lastminus] + A_cum[n-1]
    if sadmin == -1:
        sadmin = sadness
    elif sadness < sadmin:
        sadmin = sadness
    else:
        break
print(sadmin)


Fixed submission:
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()

def sadness(a, mid):
    sad = 0
    for i in range(mid):
        sad += a[mid] - a[i]
    for i in range(mid+1,len(a)):
        sad += a[i] - a[mid]
    return sad

if n % 2 != 0:
    print(sadness(A_list, n//2))
else:
    print(min(sadness(A_list, n//2), sadness(A_list, n//2+1)))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()
A_cum = [0] * n
for i in range(n):
    if i == 0:
        A_cum[0] = A_list[0]
    else:
        A_cum[i] = A_cum[i-1] + A_list[i]
def findinfindex(sortedlist, key, l, r):
    if r - l <= 0:
        return l
    m = (l+r+1)//2
    if sortedlist[m] > key:
        return findinfindex(sortedlist, key, l, m-1)
    else:
        return findinfindex(sortedlist, key, m, r)
sadnesses=[]
for b in range(A_list[0],A_list[n-1]+1):
    lastminus = findinfindex(A_list, b, 0, n-1)
    sadness = (lastminus + 1)*b - 2*A_cum[lastminus] + A_cum[n-1] - (n - lastminus - 1)*b
    sadnesses.append(sadness)
print(min(sadnesses))


Fixed submission:
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()

def sadness(a, mid):
    sad = 0
    for i in range(mid):
        sad += a[mid] - a[i]
    for i in range(mid+1,len(a)):
        sad += a[i] - a[mid]
    return sad

if n % 2 != 0:
    print(sadness(A_list, n//2))
else:
    print(min(sadness(A_list, n//2), sadness(A_list, n//2+1)))