Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
import operator
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


class SegmentTree:
    # http://tsutaj.hatenablog.com/entry/2017/03/29/204841
    def __init__(self, size, fn=operator.add, default=0):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        """
        # size 以上である最小の 2 冪
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._tree = [default for _ in range(self._size * 2 - 1)]
        self._fn = fn

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


N = int(input())
A = list(map(int, input().split()))

st = SegmentTree(size=N, fn=fractions.gcd, default=0)
for i, a in enumerate(A):
    st.set(i, a)

ans = 0
for i in range(N):
    ans = max(ans, fractions.gcd(st.get(0, i) or 0, st.get(i + 1, N) or 0))
print(ans)


Fixed submission:
import sys
import math
import fractions

sys.setrecursionlimit(10000)
INF = float('inf')


def inp():
    return int(input())


def inl():
    return list(map(int, input().split()))


def inls():
    return input().split()


def Yesif(cond):
    print('Yes' if cond else 'No')


def YESIF(cond):
    print('YES' if cond else 'NO')


def yesif(cond):
    print('yes' if cond else 'no')


N = inp()
A = inl()

ans = set()
ans.add(A[1])
gcd = A[0]
for i, a in enumerate(A):
    if i == 0:
        continue

    news = set()
    for ss in ans:
        news.add(fractions.gcd(ss, a))
    ans = news

    new_gcd = fractions.gcd(gcd, a)
    if new_gcd < gcd:
        ans.add(gcd)
    gcd = new_gcd

print(max(ans))
Buggy python submission (verdict: Time Limit Exceeded):
import math

N = int(input())
LI = []
for a in range(N):
    LI.append(int(input()))

MOD = 998244353
SUM = sum(LI)

# dp[t][r]: t までの整数を塗り分けたときに赤にしたやつの和が r となる場合の数
dp = [[0 for _ in range(SUM + 1)] for _ in range(len(LI))]
dp[0][0] = 2  # 緑か青
dp[0][LI[0]] = 1
for t in range(1, len(LI)):
    for r in range(len(dp[t])):
        dp[t][r] += dp[t - 1][r] * 2 % MOD
        dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0

# 選び方の組み合わせ数
ans = (3 ** len(LI)) % MOD
# 赤の合計が SUM / 2 以上だと三角形作れないので、選び方の合計から引く
# 緑と青が一番大きいケースも同じなので * 3
ans -= sum([dp[-1][r] for r in range(math.ceil(SUM / 2), SUM + 1)]) * 3
ans %= MOD

if SUM % 2 == 0:
    # r == g, b == 0 のケースを重複して引いてるので足したい
    # dp[t][r]: t までの整数を赤と青だけで塗り分けたときに赤にしたやつの和が r となる場合の数
    dp = [[0 for _ in range(SUM // 2 + 1)] for _ in range(len(LI))]
    dp[0][0] = 1  # 青
    dp[0][LI[0]] = 1
    for t in range(1, len(LI)):
        for r in range(len(dp[t])):
            dp[t][r] += dp[t - 1][r] % MOD
            dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0
    # 赤緑、赤青、緑青
    ans += dp[-1][SUM // 2] * 3
    ans %= MOD

print(ans)


Fixed submission:
import math

N = int(input())
LI = []
for a in range(N):
    LI.append(int(input()))

MOD = 998244353
SUM = sum(LI)

# dp[t][r]: t までの整数を塗り分けたときに赤にしたやつの和が r となる場合の数
dp = [[0 for _ in range(SUM + 1)] for _ in range(len(LI))]
dp[0][0] = 2  # 緑か青
dp[0][LI[0]] = 1
for t in range(1, len(LI)):
    for r in range(len(dp[t])):
        dp[t][r] += dp[t - 1][r] * 2 % MOD
        dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0

# 選び方の組み合わせ数
ans = (3 ** len(LI)) % MOD
# 赤の合計が SUM / 2 以上だと三角形作れないので、選び方の合計から引く
# 緑と青が一番大きいケースも同じなので * 3
ans -= sum([dp[-1][r] for r in range(math.ceil(SUM / 2), SUM + 1)]) * 3
ans %= MOD

if SUM % 2 == 0:
    # r == g, b == 0 のケースを重複して引いてるので足したい
    # dp[t][r]: t までの整数を赤と青だけで塗り分けたときに赤にしたやつの和が r となる場合の数
    dp = [[0 for _ in range(SUM // 2 + 1)] for _ in range(len(LI))]
    dp[0][0] = 1  # 青
    dp[0][LI[0]] = 1
    for t in range(1, len(LI)):
        for r in range(len(dp[t])):
            dp[t][r] += dp[t - 1][r] % MOD
            dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0
    # 赤緑、赤青、緑青
    ans += dp[-1][SUM // 2] * 3
    ans %= MOD

print(ans)
Buggy python submission (verdict: Runtime Error):
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")


a, b, c = list(map(int, sys.stdin.readline().split()))
if a==b==c:
    print('Yes')
else:
    print('No')



Fixed submission:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")


a, b, c = list(map(int, sys.stdin.readline().split()))
if a==b==c:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from fractions import gcd
from functools import lru_cache, reduce

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, A, B, C = list(map(int, sys.stdin.readline().split()))
L = [int(sys.stdin.readline()) for _ in range(N)]

L = np.array(L)

# 全部試す
choosing = list(itertools.product([0, 1, 2, 3], repeat=N))
# 0: 選ばない
# 1: 竹 A にする
# 2: 竹 B にする
# 3: 竹 C にする
ans = INF
for choose in np.array(choosing):
    a = L[choose == 1]
    b = L[choose == 2]
    c = L[choose == 3]
    if len(a) == 0 or len(b) == 0 or len(c) == 0:
        continue
    s = 0
    s += abs(A - a.sum()) + (len(a) - 1) * 10
    s += abs(B - b.sum()) + (len(b) - 1) * 10
    s += abs(C - c.sum()) + (len(c) - 1) * 10
    ans = min(ans, s)
print(ans)


Fixed submission:
import functools
import itertools

import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


def count_mp(target, sizes):
    return (len(sizes) - 1) * 10 + abs(target - sum(sizes))


N, A, B, C = map(int, input().split())
sizes = []
for _ in range(N):
    sizes.append(int(input()))

ans = INF
for allocs in itertools.product('abc_', repeat=N):
    a = []
    b = []
    c = []
    mp = 0
    for i, al in enumerate(allocs):
        if al == 'a':
            a.append(sizes[i])
        if al == 'b':
            b.append(sizes[i])
        if al == 'c':
            c.append(sizes[i])
    if not a or not b or not c:
        continue
    ans = min(ans, count_mp(A, a) + count_mp(B, b) + count_mp(C, c))
    if ans == 0:
        break
print(ans)
Buggy python submission (verdict: Runtime Error):
n, _ = map(int, input().split())
numbers = list(map(int, input().split()))
reqs = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}

memo = {}


def max_counts(a, b):
    """
    a と b 大きい方を返す
    :param a: solve() の返り値
    :param b: solve() の返り値
    :return:
    """
    if a is None:
        return b
    if b is None:
        return a
    # 桁数は大きいほうが大きい
    if sum(a) > sum(b):
        return a
    if sum(a) < sum(b):
        return b
    # 桁数が同じなら、大きい数字の多いほうが大きい
    for a_c, b_c in zip(reversed(a), reversed(b)):
        if a_c > b_c:
            return a
        if a_c < b_c:
            return b
    return a


def solve(n):
    """
    n 本のマッチを使ったときの最大の整数の 0 から 9 までの使用回数をリストで返す
    :param n:
    :rtype: list of int
    """
    if n in memo:
        return memo[n]
    if n == 0:
        return [0 for _ in range(10)]
    if n < 0:
        return None

    res = None
    for num in numbers:
        counts = solve(n - reqs[num])
        if counts:
            res = max_counts(res, counts[:num] + [counts[num] + 1] + counts[num + 1:])

    memo[n] = res
    return res


result_counts = solve(n)
ans = ''
for num in range(9, 0, -1):
    for _ in range(result_counts[num]):
        ans += str(num)
print(ans)


Fixed submission:
n, _ = map(int, input().split())
numbers = list(map(int, input().split()))
reqs = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6,
}

memo = {}


def max_counts(a, b):
    """
    a と b 大きい方を返す
    :param a: solve() の返り値
    :param b: solve() の返り値
    :return:
    """
    if a is None:
        return b
    if b is None:
        return a
    # 桁数は大きいほうが大きい
    if sum(a) > sum(b):
        return a
    if sum(a) < sum(b):
        return b
    # 桁数が同じなら、大きい数字の多いほうが大きい
    for a_c, b_c in zip(reversed(a), reversed(b)):
        if a_c > b_c:
            return a
        if a_c < b_c:
            return b
    return a


# https://atcoder.jp/contests/abc118/submissions/4911280
# DP 版
memo[0] = [0 for _ in range(10)]
for i in range(n):
    if i in memo:
        for num in numbers:
            next_n = i + reqs[num]
            next_counts = memo[next_n] if next_n in memo else None
            if next_n <= n:
                memo[next_n] = max_counts(
                    next_counts,
                    memo[i][:num] + [memo[i][num] + 1] + memo[i][num + 1:]
                )

ans = ''
for num in range(9, 0, -1):
    for _ in range(memo[n][num]):
        ans += str(num)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]
A = np.array(A, dtype=int)

# dp[i]: i まで見たときの答えの最小値
# dp[i][0]: どこも通ってない
# dp[i][1]: D まで通った
# dp[i][2]: S まで通った
# dp[i][3]: T まで通った
# dp[i][4]: U まで通った
dp = np.zeros((N, 5), dtype=int)

dp[:, 0] = A.cumsum()
dp[0, 1] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0, 2] = int(A[0] % 2 != 1)
dp[0, 3] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0, 4] = A[0]
for i in range(1, N):
    dp[i, 1] = dp[i - 1, :1 + 1].min() + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i, 2] = dp[i - 1, :2 + 1].min() + int(A[i] % 2 != 1)
    dp[i, 3] = dp[i - 1, :3 + 1].min() + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i, 4] = dp[i - 1, :4 + 1].min() + A[i]
print(dp[-1].min())


Fixed submission:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


def cumsum(li):
    ret = []
    sum = 0
    for i in li:
        sum += i
        ret.append(sum)
    return ret


# 解説AC
N = int(sys.stdin.readline())
A = [int(sys.stdin.readline()) for _ in range(N)]

# dp[i]: i まで見たときの答えの最小値
# dp[i][0]: どこも通ってない
# dp[i][1]: D まで通った
# dp[i][2]: S まで通った
# dp[i][3]: T まで通った
# dp[i][4]: U まで通った
dp = [[0] * 5 for _ in range(N)]
for i, a in enumerate(cumsum(A)):
    dp[i][0] = a
dp[0][1] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0][2] = int(A[0] % 2 != 1)
dp[0][3] = int((A[0] % 2 != 0) + (A[0] == 0) * 2)
dp[0][4] = A[0]

for i in range(1, N):
    dp[i][ 1] = min(dp[i - 1][ :1 + 1]) + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i][ 2] = min(dp[i - 1][ :2 + 1]) + int(A[i] % 2 != 1)
    dp[i][ 3] = min(dp[i - 1][ :3 + 1]) + int((A[i] % 2 != 0) + (A[i] == 0) * 2)
    dp[i][ 4] = min(dp[i - 1][ :4 + 1]) + A[i]
print(min(dp[-1]))
Buggy python submission (verdict: Runtime Error):
import heapq

INF = float('inf')
n, k = map(int, input().split())
sushi = {}

for _ in range(n):
    t, d = map(int, input().split())
    if t not in sushi:
        sushi[t] = []
    sushi[t].append(d)

for s in sushi.values():
    s.sort(reverse=True)

eat_counts = {s: 0 for s in sushi.keys()}

# まだ食べてないやつ
news = []
# リピート
repeats = []
# 食べた履歴
eats = []

# 各寿司の一番おいしいやつを heap へ
for name, deli_li in sushi.items():
    # (-おいしさ, name)
    heapq.heappush(news, (-deli_li[0], name))

sum_deli = 0
variety = 0

for _ in range(k):
    # おいしいやつから食べる
    if news and (not repeats or news[0] <= repeats[0]):
        deli, name = heapq.heappop(news)
        variety += 1
    else:
        deli, name = heapq.heappop(repeats)

    sum_deli += -deli
    eat_counts[name] += 1
    heapq.heappush(eats, (-deli, name))
    if eat_counts[name] < len(sushi[name]):
        heapq.heappush(repeats, (-sushi[name][eat_counts[name]], name))

# 美味しいやつから順に食べた
# 種類増やしたらもっと得点上がるか確かめる
ans = sum_deli + variety ** 2
while True:
    if not news:
        break

    # 食べたやつポイント小さいやつから置き換えたい
    ate_min_deli, ate_min_name = heapq.heappop(eats)
    eat_counts[ate_min_name] -= 1
    if eat_counts[ate_min_name] <= 0:
        # これは種類減っちゃうからだめ
        continue

    sum_deli -= ate_min_deli

    deli, name = heapq.heappop(news)
    variety += 1
    sum_deli += -deli
    eat_counts[name] += 1

    ans = max(ans, sum_deli + variety ** 2)

print(ans)


Fixed submission:
import heapq

INF = float('inf')
n, k = map(int, input().split())
sushi = {}

for _ in range(n):
    t, d = map(int, input().split())
    if t not in sushi:
        sushi[t] = []
    sushi[t].append(d)

for s in sushi.values():
    s.sort(reverse=True)

eat_counts = {s: 0 for s in sushi.keys()}

# まだ食べてないやつ
news = []
# リピート
repeats = []
# 食べた履歴
eats = []

# 各寿司の一番おいしいやつを heap へ
for name, deli_li in sushi.items():
    # (-おいしさ, name)
    heapq.heappush(news, (-deli_li[0], name))

sum_deli = 0
variety = 0

for _ in range(k):
    # おいしいやつから食べる
    if news and (not repeats or news[0] <= repeats[0]):
        deli, name = heapq.heappop(news)
        variety += 1
    else:
        deli, name = heapq.heappop(repeats)

    sum_deli += -deli
    eat_counts[name] += 1
    heapq.heappush(eats, (-deli, name))
    if eat_counts[name] < len(sushi[name]):
        heapq.heappush(repeats, (-sushi[name][eat_counts[name]], name))

# 美味しいやつから順に食べた
# 種類増やしたらもっと得点上がるか確かめる
ans = sum_deli + variety ** 2
while True:
    if not news or not eats:
        break

    # 食べたやつポイント小さいやつから置き換えたい
    ate_min_deli, ate_min_name = heapq.heappop(eats)
    eat_counts[ate_min_name] -= 1
    if eat_counts[ate_min_name] <= 0:
        # これは種類減っちゃうからだめ
        continue

    sum_deli -= ate_min_deli

    deli, name = heapq.heappop(news)
    variety += 1
    sum_deli += -deli
    eat_counts[name] += 1

    ans = max(ans, sum_deli + variety ** 2)

print(ans)
Buggy python submission (verdict: Runtime Error):
import functools
import math

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper


print(inp() + inp() // 2)

Fixed submission:
import functools
import math

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper


x, y = inl()
print(x+y // 2)
Buggy python submission (verdict: Runtime Error):
import functools
import math

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper


n = inp()
if n == 1:
    print ("Hello World")

a = inp()
b = inp()
print(a+b)


Fixed submission:
import functools
import math

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper


n = inp()
if n == 1:
    print ("Hello World")
    exit()

a = inp()
b = inp()
print(a+b)
Buggy python submission (verdict: Runtime Error):
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


S = sys.stdin.buffer.readline().decode().rstrip()
K = int(sys.stdin.buffer.readline())

i = 0
while S[i] == '1':
    i += 1
if K <= i:
    print('1')
else:
    print(S[i])


Fixed submission:
S = input()
K = int(input())


count1 = 0
for c in S:
    if c == '1':
        count1 += 1
    else:
        break
next_c = c

if K <= count1:
    print('1')
else:
    print(next_c)
Buggy python submission (verdict: Time Limit Exceeded):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def tleft(fn, lo, hi):
    """
    fn の結果が最も小さくなるインデックスを三分探索する
    :param callable fn:
    :param int lo: 最小のインデックス
    :param int hi: 最大のインデックス + 1
    :return: lo <= ret < hi
    """
    left = lo
    right = hi
    while abs(right - left) >= 3:
        r1 = (left * 2 + right) // 3
        r2 = (left + right * 2) // 3
        if fn(r1) <= fn(r2):
            right = r2
        else:
            left = r1
    if left + 1 >= hi or fn(left) <= fn(left + 1):
        return left
    if left + 2 >= hi or fn(left + 1) <= fn(left + 2):
        return left + 1
    return left + 2


def cost(n):
    return np.abs(A - (np.arange(N) + n)).sum()


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

i = tleft(cost, int(-1e10), int(1e10))
ans = int(cost(i))
print(ans)


Fixed submission:
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import string
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

A = np.array(A, dtype=int)
D = A - np.arange(N)
print(int(np.abs(D - np.median(D)).sum()))