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


INF = float('inf')


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


N, K = inpl()

A = [i + 1 for i in range(N)]

ans = 0
for a in A:
    if (2 * a) % K != 0: continue
    if a == K:
        mod = 0
    elif a > K:
        mod = abs(K - a) % K
    else:
        mod = a
    X = [x for x in A if (x + mod) % K == 0]
    if a in X: ans += len(X) ** 2
print(ans)

Fixed submission:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, k = LI()

if k % 2 == 1:
    print((n // k) ** 3)
else:
    print((n // k) ** 3 + (((n // (k // 2)) - (n // k)) ** 3))
Buggy python submission (verdict: Runtime Error):
# coding:utf-8

S = input()
K = int(input())

if K == 1:
    print(S[0])
else:
    S5000 = ''
    for i in range(len(S)):
        s = S[i]
        if s == '1':
            continue
        else:
            digit = i
            tmp = s
            break
    else:
        digit = len(S)

if K <= digit:
    print('1')
else:
    print(tmp)

Fixed submission:
# coding:utf-8

S = input()
K = int(input())

for i in range(K):
    if S[i] != '1':
        print(S[i])
        break
else:
    print('1')

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

S = input()
K = int(input())

if K == 1:
    print(S[0])
else:
    S5000 = ''
    for i in range(len(S)):
        s = S[i]
        if s == '1':
            continue
        else:
            digit = i
            tmp = s
            break

if K <= digit:
    print('1')
else:
    print(tmp)

Fixed submission:
# coding:utf-8

S = input()
K = int(input())

for i in range(K):
    if S[i] != '1':
        print(S[i])
        break
else:
    print('1')
Buggy python submission (verdict: Runtime Error):
# coding:utf-8

n = input()

if n == 0:
    print(0)
    exit()

ans = ''
while abs(n) > 0:
    if n % 2 != 0:
        ans += '1'
        n -= 1
        n //= -2
    else:
        ans += '0'
        n //= -2

print(ans[::-1])

Fixed submission:
#coding:utf-8


n = int(input())

ans = ''
while(n != 0):
    if n % 2 != 0:
        n -= 1
        ans = '1' + ans
    else:
        ans = '0' + ans

    n /= -2

if ans == '': ans = '0'

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

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

n,m = inpl()
A = inpl()

B = []
tmp = 0
for a in A:
    tmp += a
    B.append(tmp)

ans = 0

for i in range(n):
    if B[i] % m == 0: ans += 1

for i in range(1,n):
    for j in range(0,i):
        if (B[i] - B[j]) % m == 0: ans += 1

print(ans)

Fixed submission:
# coding:utf-8


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


N, M = inpl()
A = inpl()

S = [0]
for i in range(N):
    S.append((S[-1] + A[i]) % M)
del S[0]

D = dict()
D[0] = 0
for i in range(N):
    if S[i] in D:
        D[S[i]] += 1
    else:
        D[S[i]] = 1

ans = 0
for num in D:
    tmp = D[num]
    # cmb(x, 2)を計算
    ans += tmp * (tmp - 1) // 2

# l, rが等しく（1箱で）分配できるパターンを最後に足す
ans += D[0]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# coding:utf-8

INF = float('inf')
MOD = 10 ** 9 + 7


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


# aのp乗を求めるアルゴリズム
# MOD版
def pow_mod(a, p):
    if p == 0: return 1
    if p < 0: return 0

    if p % 2 == 0:
        half_p = p // 2
        half = pow_mod(a, half_p)
        return half * half % MOD
    else:
        return a * pow_mod(a, p - 1) % MOD


S = input()

# dp = [[0 for _ in range(4)] for _ in range(len(S) + 1)]
# dp = [len(S)][3] = 1
# for i in range(3):
#     dp[len(S)][i] = 0

A = [-INF for _ in range(len(S))]
C = A[:]
Q = A[:]

A[0] = 1 if S[0] == 'A' else 0
C[0] = 1 if S[0] == 'C' else 0
Q[0] = 1 if S[0] == '?' else 0

for i in range(1, len(S)):
    A[i] = A[i - 1] + 1 if S[i] == 'A' else A[i - 1]
    C[i] = C[i - 1] + 1 if S[i] == 'C' else C[i - 1]
    Q[i] = Q[i - 1] + 1 if S[i] == '?' else Q[i - 1]

# print(A)
# print(C)
# print(Q)
ans = 0
for i in range(1, len(S) - 1):
    if S[i] == 'A' or S[i] == 'C':
        continue

    # A, B, Cの個数
    ans += A[i - 1] * (C[-1] - C[i]) * pow_mod(3, Q[i - 1] + Q[-1] - Q[i])
    # ?, B, Cの個数
    ans += Q[i - 1] * (C[-1] - C[i]) * pow_mod(3, Q[i - 1] - 1 + Q[-1] - Q[i])
    # A, B, ?の個数
    ans += A[i - 1] * (Q[-1] - Q[i]) * pow_mod(3, Q[i - 1] + Q[-1] - Q[i] - 1)
    # ?, B, ?の個数
    ans += Q[i - 1] * (Q[-1] - Q[i]) * pow_mod(3, Q[i - 1] + Q[-1] - Q[i] - 2)

    ans %= MOD

print(ans)


Fixed submission:
# coding:utf-8

INF = float('inf')
MOD = 10 ** 9 + 7


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


# aのp乗を求めるアルゴリズム
# MOD版
def pow_mod(a, p):
    if p == 0: return 1
    if p < 0: return 0

    if p % 2 == 0:
        half_p = p // 2
        half = pow_mod(a, half_p)
        return half * half % MOD
    else:
        return a * pow_mod(a, p - 1) % MOD


S = input()

# dp = [[0 for _ in range(4)] for _ in range(len(S) + 1)]
# dp = [len(S)][3] = 1
# for i in range(3):
#     dp[len(S)][i] = 0

A = [-INF for _ in range(len(S))]
C = A[:]
Q = A[:]

A[0] = 1 if S[0] == 'A' else 0
C[0] = 1 if S[0] == 'C' else 0
Q[0] = 1 if S[0] == '?' else 0

for i in range(1, len(S)):
    A[i] = A[i - 1] + 1 if S[i] == 'A' else A[i - 1]
    C[i] = C[i - 1] + 1 if S[i] == 'C' else C[i - 1]
    Q[i] = Q[i - 1] + 1 if S[i] == '?' else Q[i - 1]

pow_three = [1]
for i in range(Q[-1]):
    tmp = pow_three[-1] * 3
    tmp %= MOD
    pow_three.append(tmp)

ans = 0
for i in range(1, len(S) - 1):
    if S[i] == 'A' or S[i] == 'C':
        continue

    # A, B, Cの個数
    tmp = Q[i - 1] + Q[-1] - Q[i]
    if tmp < 0: tmp = 0
    ans += A[i - 1] * (C[-1] - C[i]) * pow_three[tmp]
    # ?, B, Cの個数
    tmp = Q[i - 1] - 1 + Q[-1] - Q[i]
    if tmp < 0: tmp = 0
    ans += Q[i - 1] * (C[-1] - C[i]) * pow_three[tmp]
    # A, B, ?の個数
    tmp = Q[i - 1] + Q[-1] - Q[i] - 1
    if tmp < 0: tmp = 0
    ans += A[i - 1] * (Q[-1] - Q[i]) * pow_three[tmp]
    # ?, B, ?の個数
    tmp = Q[i - 1] + Q[-1] - Q[i] - 2
    if tmp < 0: tmp = 0
    ans += Q[i - 1] * (Q[-1] - Q[i]) * pow_three[tmp]

    ans %= MOD

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

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

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def lcm(a, b):
    return (a * b) // gcd(a, b)

def func(x, A):
    ans = 0
    for y in A:
        ans += x%y
    return ans

def hoge(A):
    B = []
    for i in range(len(A)-1):
        for j in range(len(A)-i-1):
            tmp = lcm(A[i], A[i+1+j])
            if tmp not in B: B.append(tmp)
    return B

max_lcm = 0
B = []
for i in range(n-1):
    for j in range(n-i-1):
        tmp = lcm(A[i], A[i+1+j])
        if tmp not in B: B.append(tmp)

while(len(B) > 1):
    B = hoge(B)

print(func(B[0]-1, A))


Fixed submission:
n = int(input())
A = list(map(int, input().split()))
print(sum(A) - n)
Buggy python submission (verdict: Time Limit Exceeded):
# coding:utf-8

INF = float('inf')


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


def binary_search(A, x):
    low = 0
    high = len(A) - 1
    mid = (low + high) // 2

    while low <= high:
        if A[mid] == x:
            break
        elif A[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
        mid = (low + high) // 2

    if mid < 0:
        return 0
    else:
        return mid


N = int(input())

A = inpl()
B = A[:]

# 累積和
for i in range(1, N):
    B[i] = B[i] + B[i - 1]

ans = INF
for mid in range(2, N - 1):
    L = B[:mid]
    R = B[mid:]
    R = [R[i] - L[-1] for i in range(len(R))]
    # print(L)
    # print(R)

    sum_list = []
    for li in [L, R]:
        if len(li) == 2:  # R, Lの要素数が2の場合の分け方は1通り
            sum_list.append(li[0])
            sum_list.append(li[1] - li[0])
            continue

        # 真ん中の切れ込みが固定されている時のRとLの切れ込みの決定
        mid = binary_search(li, li[-1] // 2)

        diff1 = abs(2 * li[mid] - li[-1])
        diff2 = abs(2 * li[mid + 1] - li[-1])

        if diff1 < diff2:
            sum_list.append(li[mid])
            sum_list.append(li[-1] - li[mid])
        else:
            sum_list.append(li[mid + 1])
            sum_list.append(li[-1] - li[mid + 1])

    ans = min(ans, max(sum_list) - min(sum_list))

print(ans)

Fixed submission:
# coding:utf-8

INF = float('inf')


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


N = int(input())

A = inpl()
B = A[:]

# 累積和
for i in range(1, N):
    B[i] = B[i] + B[i - 1]

ans = INF
mid_l = 0
mid_r = 2
t = B[-1]
for mid in range(1, N - 1):
    while mid_l < mid and abs(2 * B[mid_l] - B[mid]) >= abs(2 * B[mid_l + 1] - B[mid]):
        mid_l += 1
    while mid_r < N - 1 and abs(2 * B[mid_r] - B[mid] - t) >= abs(2 * B[mid_r + 1] - B[mid] - t):
        mid_r += 1

    p = B[mid_l]
    q = B[mid] - p
    r = B[mid_r] - p - q
    s = t - r - p - q

    ans = min(ans, max(p, q, r, s) - min(p, q, r, s))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
substrings = []
for i in range(len(s)):
    for j in range(len(s)-i):
        if s[i:i+j+1] not in substrings: substrings.append(s[i:i+j+1])

substrings.sort()
print(substrings[k-1])

Fixed submission:
s = input()
k = int(input())
substrings = []

for i in range(len(s)):
    for j in range(i, min(len(s), i+5)):
        if s[i:j+1] not in substrings: substrings.append(s[i:j+1])

substrings.sort()
print(substrings[k-1])
Buggy python submission (verdict: Time Limit Exceeded):
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    B = [SI() for _ in range(n)]

    res = 0
    for i in range(n):
        is_good = 1
        for h in range(n):
            for w in range(h + 1, n):
                if B[h][(w + i) % n] != B[w][(h + i) % n]:
                    is_good = 0

        if is_good:
            res += n

    return res


print(main())


Fixed submission:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    B = [SI() for _ in range(n)]

    res = 0
    for i in range(n):
        is_good = 1
        for h in range(n):
            for w in range(h + 1, n):
                if B[h][(w + i) % n] != B[w][(h + i) % n]:
                    is_good = 0
                    break

            if not is_good:
                break

        if is_good:
            res += n

    return res


print(main())

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

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    B = [SI() for _ in range(n)]

    res = 0
    for i in range(n):
        is_good = 1
        for h in range(n):
            for w in range(h + 1, n):
                if B[h][(w + i) % n] != B[w][(h + i) % n]:
                    is_good = 0
                    break

            if not is_good:
                break

        if is_good:
            res += n

    return res


print(main())


Fixed submission:
# coding:utf-8

import sys
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    B = [SI() for _ in range(n)]

    res = 0
    for i in range(n):
        is_good = 1
        for h in range(n):
            for w in range(h + 1, n):
                if B[h][(w + i) % n] != B[w][(h + i) % n]:
                    is_good = 0
                    break

            if not is_good:
                break

        if is_good:
            res += n

    return res


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

import sys


input = sys.stdin.readline


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


N = int(input())
A = inpl()

a = max(A)
tmp = 0
for i in range(N):
    x = A[i]
    if x == a: continue
    x = max(x, a - x)
    if tmp < a - x:
        b = A[i]
        tmp = a - x

print(a, b)


Fixed submission:
# coding:utf-8

INF = float('inf')


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


N = int(input())
A = inpl()

n = max(A)
r = max(A)
tmp = 0
for i in range(N):
    a = A[i]
    if a == n: continue
    if a < n - a: a = n - a
    if tmp <= n - a:
        r = A[i]
        tmp = n - a

print(n, r)
Buggy python submission (verdict: Runtime Error):
a, b, c = map(int, input().spilt())
print('Yes' if a + b >= c else 'No')

Fixed submission:
a, b, c = map(int, input().split())
print('Yes' if a + b >= c else 'No')
Buggy python submission (verdict: Time Limit Exceeded):
# coding:utf-8

import sys
import random
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    red = [[a + b, a, b] for a, b in (LI() for _ in range(n))]
    blue = [[a + b, a, b] for a, b in (LI() for _ in range(n))]

    ans = 0
    red.sort()
    for _ in range(n):
        red = red[-1:] + red[:-1]
        used = [0] * n
        res = 0
        for s, a, b in red:
            near = -1
            d = INF
            for i, (ss, x, y) in enumerate(blue):
                if a < x and b < y:
                    tmp = x - a + y - b
                    if tmp < d and not used[i]:
                        near = i
                        d = tmp

            if near != -1:
                used[near] = 1
                res += 1
        ans = max(ans, res)

    red.reverse()
    for _ in range(n):
        red = red[-1:] + red[:-1]
        used = [0] * n
        res = 0
        for s, a, b in red:
            near = -1
            d = INF
            for i, (ss, x, y) in enumerate(blue):
                if a < x and b < y:
                    tmp = x - a + y - b
                    if tmp < d and not used[i]:
                        near = i
                        d = tmp

            if near != -1:
                used[near] = 1
                res += 1
        ans = max(ans, res)

    for _ in range(20):
        random.shuffle(red)
        for _ in range(n):
            red = red[-1:] + red[:-1]
            used = [0] * n
            res = 0
            for s, a, b in red:
                near = -1
                d = INF
                for i, (ss, x, y) in enumerate(blue):
                    if a < x and b < y:
                        tmp = x - a + y - b
                        if tmp < d and not used[i]:
                            near = i
                            d = tmp

                if near != -1:
                    used[near] = 1
                    res += 1
            ans = max(ans, res)

    return ans


print(main())


Fixed submission:
# coding:utf-8

import sys
import random
# from collections import Counter, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    red = [LI() for _ in range(n)]
    blue = [LI() for _ in range(n)]
    blue.sort()

    used = [0] * n
    res = 0
    for a, b in blue:
        t = -1
        k = -1
        for i, (x, y) in enumerate(red):
            if used[i]:
                continue

            if x < a and b > y > t:
                t = y
                k = i

        if k != -1:
            used[k] = 1
            res += 1

    return res


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

import sys

input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


H, W, D = inpl()

num_coordinate = {}
for i in range(H):
    w = inpl()
    for j in range(W):
        num_coordinate[w[j]] = (i, j)

c_sum = {}
for d in range(1, D + 1):
    c_sum[d] = [0]

for d in range(1, D + 1):
    for n in range(d + D, H * W, D):
        c_sum[d].append(c_sum[d][-1] + abs(num_coordinate[n][0] - num_coordinate[n - D][0])
                        + abs(num_coordinate[n][1] - num_coordinate[n - D][1]))

Q = int(input())
for _ in range(Q):
    l, r = inpl()
    index = (l - 1) % D + 1
    index_l, index_r = (l - 1) // D, (r - 1) // D

    print(c_sum[index][index_r] - c_sum[index][index_l])


Fixed submission:
# coding:utf-8

import sys

input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


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


H, W, D = inpl()

num_coordinate = {}
for i in range(H):
    w = inpl()
    for j in range(W):
        num_coordinate[w[j]] = (i, j)

c_sum = {}
for d in range(1, D + 1):
    c_sum[d] = [0]

for d in range(1, D + 1):
    for n in range(d + D, H * W + 1, D):
        c_sum[d].append(c_sum[d][-1] + abs(num_coordinate[n][0] - num_coordinate[n - D][0])
                        + abs(num_coordinate[n][1] - num_coordinate[n - D][1]))

Q = int(input())
for _ in range(Q):
    l, r = inpl()
    index = (l - 1) % D + 1
    index_l, index_r = (l - 1) // D, (r - 1) // D

    print(c_sum[index][index_r] - c_sum[index][index_l])
Buggy python submission (verdict: Runtime Error):
s = input()
n = len(s)
k = 0
tmp = set()
while len(tmp) < 2:
    tmp.add(s[n // 2 + k])
    tmp.add(s[(n - 1) // 2 - k])
    k += 1
print(n // 2 + k - 1)

Fixed submission:
s = input()

n = len(s)
ans = n
for i, (c1, c2) in enumerate(zip(s[:-1], s[1:])):
    if c1 == c2:
        continue
    ans = min(ans, max(i + 1, n - i - 1))

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

import itertools

INF = float('inf')


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


def dijkstra(graph, start):
    MAX_SIZE = len(graph)
    visited = [False for _ in range(MAX_SIZE)]
    cost = [INF for _ in range(MAX_SIZE)]
    prev = [None for _ in range(MAX_SIZE)]

    cost[start] = 0
    prev[start] = start
    path = [start + 1]
    while True:
        min_cost = INF
        next = -1
        visited[start] = True
        # 頂点の選択
        for i in range(MAX_SIZE):
            if visited[i]: continue # 探索済みの頂点は飛ばす
            if graph[start][i]: # 頂点startと接続されているか判定
                dist = cost[start] + graph[start][i]
                if dist < cost[i]:
                    cost[i] = dist
                    prev[i] = start

            if cost[i] < min_cost:
                min_cost = cost[i]
                next = i

        start = next
        path.append(next + 1)
        if next == -1: break

    # print(cost)
    # print(path)
    return cost


def main():
    N, M, R = inpl()
    r = inpl()

    G = [[None for _ in range(N)] for _ in range(N)]
    for i in range(M):
        a, b, c = inpl()
        G[a - 1][b - 1] = c
        G[b - 1][a - 1] = c

    ans = INF
    for root in itertools.permutations(r, R):
        dist = 0
        for i in range(R - 1):
            dist += dijkstra(G, root[i] - 1)[root[i + 1] - 1]
        ans = min(ans, dist)

    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
# coding:utf-8

import itertools

INF = float('inf')


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


def dijkstra(graph, start):
    MAX_SIZE = len(graph)
    visited = [False for _ in range(MAX_SIZE)]
    cost = [INF for _ in range(MAX_SIZE)]
    prev = [None for _ in range(MAX_SIZE)]

    cost[start] = 0
    prev[start] = start
    path = [start + 1]
    while True:
        min_cost = INF
        next = -1
        visited[start] = True
        # 頂点の選択
        for i in range(MAX_SIZE):
            if visited[i]: continue  # 探索済みの頂点は飛ばす
            if graph[start][i]:  # 頂点startと接続されているか判定
                dist = cost[start] + graph[start][i]
                if dist < cost[i]:
                    cost[i] = dist
                    prev[i] = start

            if cost[i] < min_cost:
                min_cost = cost[i]
                next = i

        start = next
        path.append(next + 1)
        if next == -1: break

    # print(cost)
    # print(path)
    return cost


def main():
    N, M, R = inpl()
    r = inpl()

    G = [[None for _ in range(N)] for _ in range(N)]
    for i in range(M):
        a, b, c = inpl()
        G[a - 1][b - 1] = c
        G[b - 1][a - 1] = c

    min_cost = {}
    for s in r:
        min_cost[str(s)] = dijkstra(G, s - 1)

    ans = INF
    for root in itertools.permutations(r, R):
        dist = 0
        for i in range(R - 1):
            s = str(root[i])
            dist += min_cost[s][root[i + 1] - 1]
        ans = min(ans, dist)

    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, T = map(int, raw_input().split())
    t = map(int, raw_input().split())
    c = t[-1] + T + 1
    a = [0 for _ in xrange(c)]
    for i in t:
        a[i] += 1
        a[i+T] -= 1

    count = 0
    for i in xrange(c):
        if(0 < i):
            a[i] += a[i - 1]
            if(a[i] != 0): count += 1

    if(a[0] != 0): count += 1
    print count
    return 0

if __name__ == '__main__':
    main()

Fixed submission:
n, t = map(int, input().split())
T = list(map(int, input().split()))

ans = t
for t1, t2 in zip(T[:-1], T[1:]):
  ans += min(t2 - t1, t)

print(ans)