Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def main():
    x, y, z, k = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    b = sorted(list(map(int, input().split())), reverse=True)
    c = sorted(list(map(int, input().split())), reverse=True)
    count = min(x * z, k)
    ac = list()
    ans = list()

    for ai in a:
        for ci in c:
            ac.append(ai + ci)

    for bi in b:
        for ac_i in sorted(ac, reverse=True)[:count]:
            ans.append(bi + ac_i)

    for j in sorted(ans, reverse=True)[:k]:
        print(j)


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    x, y, z, k = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    b = sorted(list(map(int, input().split())), reverse=True)
    c = sorted(list(map(int, input().split())), reverse=True)
    ac = list()

    for ai in a:
        for ci in c:
            ac.append(ai + ci)

    count = min(x * z, k)
    acs = sorted(ac, reverse=True)[:count]
    ans = list()

    for bi in b:
        for ac_i in acs:
            ans.append(bi + ac_i)

    for j in sorted(ans, reverse=True)[:k]:
        print(j)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def main():
    x, y, z, k = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    b = sorted(list(map(int, input().split())), reverse=True)
    c = sorted(list(map(int, input().split())), reverse=True)
    count = min(x * z, k)
    ac = list()
    ans = list()

    for ai in a:
        for ci in c:
            ac.append(ai + ci)

    for bi in b:
        for ac_i in sorted(ac, reverse=True)[:count]:
            ans.append(bi + ac_i)

    for j in sorted(ans, reverse=True)[:k]:
        print(j)


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    x, y, z, k = map(int, input().split())
    a = sorted(list(map(int, input().split())), reverse=True)
    b = sorted(list(map(int, input().split())), reverse=True)
    c = sorted(list(map(int, input().split())), reverse=True)
    ac = list()

    for ai in a:
        for ci in c:
            ac.append(ai + ci)

    count = min(x * z, k)
    acs = sorted(ac, reverse=True)[:count]
    ans = list()

    for bi in b:
        for ac_i in acs:
            ans.append(bi + ac_i)

    for j in sorted(ans, reverse=True)[:k]:
        print(j)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def main():
    a, b = map(int, input().split())
    start = a
    ans = a

    if a % 2 == 0:
        if b - (a - 1) >= 4:
            start = b - (b - (a - 1) % 4)
            ans = 0
    else:
        if b - a >= 4:
            start = b - (b - a) % 4
            ans = a

    for i in range(start + 1, b + 1):
        ans ^= i

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    a, b = map(int, input().split())
    start = a
    ans = a

    if a % 2 == 0:
        if b - (a - 1) >= 4:
            start = b - ((b - (a - 1)) % 4)
            ans = 0
    else:
        if b - a >= 4:
            start = b - ((b - a) % 4)
            ans = a

    for i in range(start + 1, b + 1):
        ans ^= i

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def main():
    from bisect import bisect_right

    a, b, q = map(int, input().split())
    s = [-float('inf')] + [int(input()) for _ in range(a)] + [float('inf')]
    t = [-float('inf')] + [int(input()) for _ in range(b)] + [float('inf')]

    # See:
    # https://img.atcoder.jp/abc119/editorial.pdf
    for _ in range(q):
        x = int(input())
        s_right = bisect_right(s, x)
        s_left = s_right - 1
        t_right = bisect_right(t, x)
        t_left = t_right - 1
        ans = float('inf')

        for si in [s[s_left], s[s_right]]:
            for ti in [t[t_left], t[t_right]]:
                ans = min(ans, abs(si - x) + abs(si - ti), abs(ti - x) + abs(si - ti))

        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    from bisect import bisect_right

    a, b, q = map(int, input().split())
    s = [-float('inf')] + [int(input()) for _ in range(a)] + [float('inf')]
    t = [-float('inf')] + [int(input()) for _ in range(b)] + [float('inf')]

    # See:
    # https://img.atcoder.jp/abc119/editorial.pdf
    for _ in range(q):
        x = int(input())
        s_right = bisect_right(s, x)
        s_left = s_right - 1
        t_right = bisect_right(t, x)
        t_left = t_right - 1
        ans = float('inf')

        for si in [s[s_left], s[s_right]]:
            for ti in [t[t_left], t[t_right]]:
                ans = min(ans, abs(si - x) + abs(si - ti), abs(ti - x) + abs(si - ti))

        print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-


def main():
    from heapq import heappush, heappop

    n = int(input())
    a = list(map(int, input().split()))
    elements = list()

    for ai in a:
        heappush(elements, ai)

    while len(elements) >= 2:
        a_min = heappop(elements)

        for _ in range(len(elements)):
            aj = heappop(elements)
            aj %= a_min

            if aj != 0:
                heappush(elements, aj)

        if len(elements) == 0:
            print(a_min)
            exit()

    print(min(a_min, elements))


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    mod_a = a
    mod = min(a)
    index = 0

    while True:
        for idx, ai in enumerate(a):
            if idx != index:
                mod_a[idx] %= mod

                if 0 < mod_a[idx] < mod:
                    mod = mod_a[idx]
                    index = idx

        if mod_a.count(0) >= n - 1:
            break

    print(max(min(a), max(mod_a)))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    diff_positive = dict()
    diff_negaitive = dict()
    pos_max = 0
    nega_max = 0
    a = [0 for _ in range(n)]
    b = [0 for _ in range(n)]

    for i in range(n):
        ai, bi = map(int, input().split())
        a[i] = ai
        b[i] = bi

        if ai - bi >= 0:
            diff_positive[i] = ai - bi
            pos_max = max(pos_max, ai - bi)
        else:
            diff_negaitive[i] = bi - ai
            nega_max = max(nega_max, abs(ai - bi))

    posi = sorted(diff_positive.items(), key=lambda x: x[1], reverse=True)
    nega = sorted(diff_negaitive.items(), key=lambda x: x[1], reverse=True)
    taka_point = 0
    aoki_point = 0

    if len(posi) % 2 == 0:
        taka = posi[::2] + nega[::2]
        aoki = posi[1::2] + nega[1::2]

        for t in taka:
            taka_point += a[t[0]]

        for a in aoki:
            aoki_point += b[a[0]]

        print(taka_point - aoki_point)
    else:
        taka = posi[::2] + nega[1::2]
        aoki = posi[1::2] + nega[::2]

        for t in taka:
            taka_point += a[t[0]]

        for a in aoki:
            aoki_point += b[a[0]]

        ans1 = taka_point - aoki_point

        taka = posi[1::2] + nega[::2]
        aoki = posi[::2] + nega[1::2]

        for t in taka:
            taka_point += a[t[0]]

        for a in aoki:
            aoki_point += b[a[0]]

        ans2 = taka_point - aoki_point
        print(max(ans1, ans2))


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    dishes = list()
    ans = 0

    # See:
    # https://poporix.hatenablog.com/entry/2019/01/28/222905
    # https://misteer.hatenablog.com/entry/NIKKEI2019qual?_ga=2.121425408.962332021.1548821392-1201012407.1527836447
    for i in range(n):
        ai, bi = map(int, input().split())
        dishes.append(tuple([ai + bi, ai, bi]))

    for index, dish in enumerate(sorted(dishes, reverse=True)):
        if index % 2 == 0:
            ans += dish[1]
        else:
            ans -= dish[2]

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [float('inf') for _ in range(n)]
    cost[n - 1] = 0

    for j in range(2, n + 1):
        for i in range(max(1, j - k), j + 1):
            cost[n - j] = min(cost[n - j],
                              cost[n - i] + abs(h[n - i] - h[n - j]))

    print(cost[0])


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [float('inf') for _ in range(n)]
    cost[n - 1] = 0

    for j in range(2, n + 1):
        for i in range(max(1, j - k), j + 1):
            cost[n - j] = min(cost[n - j],
                              cost[n - i] + abs(h[n - i] - h[n - j]))

    print(cost[0])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def main():
    n, w = map(int, input().split())
    ws = [0 for _ in range(n)]
    vs = [0 for _ in range(n)]
    dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

    for i in range(n):
        wi, vi = map(int, input().split())
        ws[i] = wi
        vs[i] = vi

    for i in range(n):
        for sum_w in range(w + 1):
            if sum_w - ws[i] >= 0:
                dp[i + 1][sum_w] = max(dp[i + 1][sum_w],
                                       dp[i][sum_w - ws[i]] + vs[i])

            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])

    print(dp[n][w])


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    n, w = map(int, input().split())
    ws = [0 for _ in range(n)]
    vs = [0 for _ in range(n)]
    dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

    for i in range(n):
        wi, vi = map(int, input().split())
        ws[i] = wi
        vs[i] = vi

    for i in range(n):
        for sum_w in range(w + 1):
            if sum_w - ws[i] >= 0:
                dp[i + 1][sum_w] = max(dp[i + 1][sum_w],
                                       dp[i][sum_w - ws[i]] + vs[i])

            dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])

    print(dp[n][w])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def main():
    s = list(input())
    n = len(s)
    t = list(input())
    m = len(t)
    # LCSの長さを状態として持つ
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d
    # LCSの求め方は蟻本のpp.56-57も参照
    # △文字列s, tを二次元配列の形で扱う
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    ans = ''
    i = n
    j = m

    # △復元
    # dp tableの値を見てどこから更新されたかを特定
    while i > 0 and j > 0:
        # (i - 1, j) -> (i, j)
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        # (i, j - 1) -> (i, j)
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        # (i - 1, j - 1) -> (i, j)
        else:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    s = list(input())
    n = len(s)
    t = list(input())
    m = len(t)
    # LCSの長さを状態として持つ
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d
    # LCSの求め方は蟻本のpp.56-57も参照
    # △文字列s, tを二次元配列の形で扱う
    for i in range(n):
        for j in range(m):
            if s[i] == t[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

    ans = ''
    i = n
    j = m

    # △復元
    # dp tableの値を見てどこから更新されたかを特定
    while i > 0 and j > 0:
        # (i - 1, j) -> (i, j)
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        # (i, j - 1) -> (i, j)
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        # (i - 1, j - 1) -> (i, j)
        else:
            ans = s[i - 1] + ans
            i -= 1
            j -= 1

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(n + 3)] for _ in range(n + 3)]

    # 初期化
    dp[0][0] = 1.0

    # KeyInsight
    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # ・状態：確率
    # ・すべての候補，条件に一致する候補をdpで管理
    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#i-%E5%95%8F%E9%A1%8C---coins
    for i in range(n):
        for j in range(i + 1):
            # 表
            dp[i + 1][j + 1] += dp[i][j] * p[i]
            # 裏
            dp[i + 1][j] += dp[i][j] * (1 - p[i])

    ans = 0

    # 表が多い場合のみ計算
    for j in range((n + 1) // 2, n + 1):
        ans += dp[n][j]

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(n + 100)] for _ in range(n + 100)]

    # 初期化
    dp[0][0] = 1.0

    # KeyInsight
    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # ・状態：確率
    # ・すべての候補，条件に一致する候補をdpで管理
    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#i-%E5%95%8F%E9%A1%8C---coins
    for i in range(n):
        for j in range(i + 1):
            # 表
            dp[i + 1][j + 1] += dp[i][j] * p[i]
            # 裏
            dp[i + 1][j] += dp[i][j] * (1 - p[i])

    ans = 0

    # 表が多い場合のみ計算
    for j in range((n + 1) // 2, n + 1):
        ans += dp[n][j]

    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(n + 100)] for _ in range(n + 100)]

    # 初期化
    dp[0][0] = 1.0

    # KeyInsight
    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # ・状態：確率
    # ・すべての候補，条件に一致する候補をdpで管理
    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#i-%E5%95%8F%E9%A1%8C---coins
    for i in range(n):
        for j in range(i + 1):
            # 表
            dp[i + 1][j + 1] += dp[i][j] * p[i]
            # 裏
            dp[i + 1][j] += dp[i][j] * (1 - p[i])

    ans = 0

    # 表が多い場合のみ計算
    for j in range((n + 1) // 2, n + 1):
        ans += dp[n][j]

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    n = int(input())
    p = list(map(float, input().split()))
    dp = [[0 for _ in range(n + 100)] for _ in range(n + 100)]

    # 初期化
    dp[0][0] = 1.0

    # KeyInsight
    # dp[i][j] := 最初の i 枚のコインを投げたときに、表が j 枚となる確率
    # ・状態：確率
    # ・すべての候補，条件に一致する候補をdpで管理
    # See:
    # https://qiita.com/drken/items/03c7db44ccd27820ea0d#i-%E5%95%8F%E9%A1%8C---coins
    for i in range(n):
        for j in range(i + 1):
            # 表
            dp[i + 1][j + 1] += dp[i][j] * p[i]
            # 裏
            dp[i + 1][j] += dp[i][j] * (1 - p[i])

    ans = 0

    # 表が多い場合のみ計算
    for j in range((n + 1) // 2, n + 1):
        ans += dp[n][j]

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def main():
    # 再帰関数を使うときは，その上限回数に注意
    # https://docs.python.org/ja/3/library/sys.html#sys.setrecursionlimit
    from sys import setrecursionlimit

    setrecursionlimit(5 * 10 ** 7)

    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    memo = [[-1 for _ in range(3)] for _ in range(k + 1)]

    def rec(i, j):
        if memo[i][j] != -1:
            return memo[i][j]

        result = 0

        for ak in a:
            if ak <= i:
                if rec(i - ak, (j + 1) % 2) == 0:
                    result = 1
                    break

        memo[i][j] = result

        return memo[i][j]

    ans = rec(k, 0)

    if ans == 1:
        print('First')
    else:
        print('Second')


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [0 for _ in range(k + 1)]

    # See:
    # https://atcoder.jp/contests/dp/submissions/3956066
    for i in range(k):
        if dp[i]:
            continue

        for ai in a:
            if i + ai > k:
                break

            dp[i + ai] = 1

    if dp[-1] == 1:
        print('First')
    else:
        print('Second')


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def main():
    from math import sqrt

    n, p = map(int, input().split())
    ans = 1
    numbers = set()

    for i in range(1, int(sqrt(p)) + 1):
        a, b = divmod(p, i)

        if b == 0:
            numbers.add(i)
            numbers.add(a)

    for number in numbers:
        c, d = divmod(p, number ** n)

        if d == 0 and number ** n <= p:
            ans = max(ans, number)

    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def run_prime_factorization(max_number: int):
    from math import sqrt

    ans = dict()
    remain = max_number

    for j in range(2, int(sqrt(max_number)) + 1):
        if remain % j == 0:
            count = 0

            while remain % j == 0:
                count += 1
                remain //= j

            ans[j] = count

    if remain != 1:
        ans[remain] = 1

    return ans


def main():
    n, p = map(int, input().split())
    ans = 1

    # See:
    # https://www.youtube.com/watch?v=z0bIhkaSXY4
    results = run_prime_factorization(p)

    for base, exponent in results.items():
        ans *= base ** (exponent // n)

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-


def lcm(x: int, y: int):
    '''
    See:
    https://note.nkmk.me/python-gcd-lcm/
    '''
    from fractions import gcd
    return (x * y) // gcd(x, y)


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    size = lcm(n, m)
    x = ['' for _ in range(size)]

    for i in range(n):
        x[i * size // n] = s[i]

    for j in range(m):
        if x[j * size // m] == '':
            x[j * size // m] = t[j]
        elif x[j * size // m] != t[j]:
            print(-1)
            exit()

    print(size)


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def lcm(x: int, y: int):
    '''
    See:
    https://note.nkmk.me/python-gcd-lcm/
    '''
    from fractions import gcd
    return (x * y) // gcd(x, y)


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    size = lcm(n, m)
    dn = size // n
    dm = size // m
    part_s = [s[0]]
    part_t = [t[0]]
    i = dm
    j = dn

    while i < n:
        part_s.append(s[i])
        i += dm

    while j < m:
        part_t.append(t[j])
        j += dn

    for si, ti in zip(part_s, part_t):
        if si != ti:
            print(-1)
            exit()

    print(size)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-


def main():
    n, k = list(map(int, input().split()))
    x = list(map(int, input().split()))

    if x[0] < 0:
        diff = abs(x[0])

        for i in range(n):
            x[i] += diff

    print(min(x[k - 1]), x[-k])


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    n, k = list(map(int, input().split()))
    x = list(map(int, input().split()))
    ans = float('inf')

    for i in range(n - k + 1):
        left = x[i]
        right = x[i + k - 1]

        if left * right >= 0:
            ans = min(ans, max(abs(left), abs(right)))
        else:
            ans = min(ans, 2 * abs(left) + abs(right), abs(left) + 2 * abs(right))

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-


def main():
    s = input()
    k = int(input())
    one_count = 0

    for si in s:
        if si == '1':
            one_count += 1
        else:
            break

    if s[0] == '1':
        if k == 1:
            print(s[0])
        elif one_count >= k:
            print(1)
        elif one_count < k:
            print(s[k - 1])
        else:
            print(s[1])
    else:
        print(s[0])


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    s = input()
    k = int(input())
    one_count = 0

    for si in s:
        if si == '1':
            one_count += 1
        else:
            break

    if s[0] == '1':
        if k == 1:
            print(s[0])
        elif one_count >= k:
            print(1)
        elif one_count < k:
            print(s[one_count])
        else:
            print(s[1])
    else:
        print(s[0])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-


def main():
    s = input()
    k = int(input())

    if s[0] == '1':
        print(s[1])
    else:
        print(s[0])


if __name__ == '__main__':
    main()


Fixed submission:
# -*- coding: utf-8 -*-


def main():
    s = input()
    k = int(input())
    one_count = 0

    for si in s:
        if si == '1':
            one_count += 1
        else:
            break

    if s[0] == '1':
        if k == 1:
            print(s[0])
        elif one_count >= k:
            print(1)
        elif one_count < k:
            print(s[one_count])
        else:
            print(s[1])
    else:
        print(s[0])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
# AtCoder Beginner Contest


if __name__ == '__main__':
    from statistics import median

    n = int(input())
    a = list(map(int, input().split()))
    total = 0

    # See:
    # https://www.youtube.com/watch?v=UX4AuiCVtN4
    # https://beta.atcoder.jp/contests/abc102/submissions/2768315
    mod_a = sorted([ai - i for i, ai in enumerate(a, 1)])

    for i in range(n):
        total += abs(mod_a[i] - median(mod_a))

    print(int(total))


Fixed submission:
# -*- coding: utf-8 -*-
# AtCoder Beginner Contest


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    total = 0

    for i in range(n):
        a[i] -= i + 1

    sorted_a = sorted(a)
    b = sorted_a[n // 2]

    for i in range(n):
        total += abs(a[i] - b)

    print(int(total))
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    s = input()
    count = 0

    for i in range(len(s)):
        if i == 0:
            count = s[1:].count('E')
        else:
            count = min(count, s[:i].count('W') + s[i + 1:].count('E'))

    print(count)


Fixed submission:
# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    s = input()
    count = 0
    ws = [0] * n
    es = [0] * n

    for i in range(0, n):
        if s[i] == 'W':
            ws[i] = ws[i - 1] + 1
            es[i] = es[i - 1]
        else:
            es[i] = es[i - 1] + 1
            ws[i] = ws[i - 1]

    for i in range(len(s) - 1):
        if i == 0:
            count = es[-1] - es[1]
        else:
            count = min(count, (ws[i]) + (es[-1] - es[i + 1]))

    print(count)