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

[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
for i in range(m):
    tmp = a.pop(-1)
    bisect.insort(a, int(tmp / 2))
print(sum(a))

Fixed submission:
import heapq

[n, m] = [int(i) for i in input().split()]
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    tmp = heapq.heappop(a)
    heapq.heappush(a, int(tmp / 2))
print(-1 * sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
for i in range(m):
    idx = a.index(max(a))
    a[idx] = int(a[idx] / 2)
print(sum(a))


Fixed submission:
import heapq

[n, m] = [int(i) for i in input().split()]
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    tmp = heapq.heappop(a)
    heapq.heappush(a, int(tmp / 2))
print(-1 * sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
for i in range(m):
    a[a.index(max(a))] = int(a[a.index(max(a))] / 2)
    
print(sum(a))

Fixed submission:
import heapq

[n, m] = [int(i) for i in input().split()]
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    tmp = heapq.heappop(a)
    heapq.heappush(a, int(tmp / 2))
print(-1 * sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
for i in range(m):
    a[-1] = int(a[-1] / 2)
    a.sort()
print(sum(a))

Fixed submission:
import heapq

[n, m] = [int(i) for i in input().split()]
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    tmp = heapq.heappop(a)
    heapq.heappush(a, int(tmp / 2))
print(-1 * sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
for i in range(m):
    a[-1] = int(a[-1] / 2)
    a.sort()
print(sum(a))

Fixed submission:
import heapq

[n, m] = [int(i) for i in input().split()]
a = [-1 * int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    tmp = heapq.heappop(a)
    heapq.heappush(a, int(tmp / 2))
print(-1 * sum(a))
Buggy python submission (verdict: Runtime Error):
[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
for i in range(m):
    idx = a.index(max(a))
    a[idx] = int(a[idx] / 2)
print(sum(a))


Fixed submission:
[n, k] = [int(i) for i in input().split()]
total = 0
for i in range(1, n+1):
    point = i
    prob = 1/n
    while(point < k):
        point *= 2
        prob /= 2
    total += prob
print(total)

Buggy python submission (verdict: Runtime Error):
[n, m] = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
for i in range(m):
    a[-1] = int(a[-1] / 2)
    a.sort()
print(sum(a))

Fixed submission:
[n, k] = [int(i) for i in input().split()]
total = 0
for i in range(1, n+1):
    point = i
    prob = 1/n
    while(point < k):
        point *= 2
        prob /= 2
    total += prob
print(total)
Buggy python submission (verdict: Runtime Error):
[a, b, n] = [int(i) for i in input().split()]
hoge = []
for i in range(1, 101):
    if i%a==0 and i%b==0:
        hoge.append(i)
print(hoge[n-1])


Fixed submission:
[a, b, n] = [int(i) for i in input().split()]
hoge = []
for i in range(1, 101):
    if a%i==0 and b%i==0:
        hoge.append(i)
hoge.sort(reverse=True)
print(hoge[n-1])
Buggy python submission (verdict: Runtime Error):
[n, k] = [int(i) for i in input().split()]
h = np.array([int(i) for i in input().split()])
dp = [10 ** 5 for _ in range(n)]
dp[0] = 0
for i in range(n):
    for j in range(k+1):
        if i + j < n:
            dp[i + j] = min(dp[i + j] , dp[i] + abs(h[i] - h[i+j]))
print(dp[n-1])


Fixed submission:
[n, k] = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [10 ** 10 for _ in range(n)]
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    for j in range(1, min(i, k)+1):
        if i - j >= 0:
            dp[i] = min(dp[i] , dp[i-j] + abs(h[i] - h[i-j]))
print(dp[n-1])
Buggy python submission (verdict: Runtime Error):

def resolve():
    n = int(input())
    action = []
    for i in range(n):
        action.append([int(i) for i in input().split()])
    df = []
    df.append(max(action[0]))
    prev = action[0].index(max(action[0]))
    for i in range(1, n):
        tgt = max([action[i][j] for j in range(len(action[i])) if j != prev])
        prev = action[i].index(tgt)
        df.append(tgt)
    print(sum(df))

if __name__ = "__main__":
    resolve()


Fixed submission:
n = int(input())
action = []
for i in range(n):
    action.append([int(i) for i in input().split()])
dp = [[0 for _ in range(3)] for _ in range(n+1)]

for i in range(n):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i+1][k] = max(dp[i+1][k], dp[i][j] + action[i][k])
print(max(dp[n]))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = 1
b = 1
mx = 10 ** 10
while (a <= b and a * a <= n):
    if n % a == 0:
        b = int(n / a)
        mx = min(mx, max(a, b))
    a += 1
print(len(str(mx)))


Fixed submission:
[a, b, ab, x, y] = [int(i) for i in input().split()]
price = []
price.append(a * x + b * y)
if x > y:
    price.append(2 * ab * y + a * (x-y))
else:
    price.append(2 * ab * x + b * (y-x))
price.append(ab * 2 * max(x, y))
print(min(price))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = 1
b = 1
mx = 10 ** 10
while (a <= b and a <= n):
    if n % a == 0:
        b = int(n / a)
        mx = min(mx, max(a, b))
    a += 1
print(len(str(mx)))


Fixed submission:
n = int(input())
a = 1
b = 1
mx = 10 ** 10
while (a <= b and a <= 10**5):
    if n % a == 0:
        b = int(n / a)
        mx = min(mx, max(a, b))
    a += 1
print(len(str(mx)))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = 1
b = 1
mx = 10 ** 10
while (a <= b):
    if n % a == 0:
        b = int(n / a)
        mx = min(mx, max(a, b))
    a += 1
print(len(str(mx)))

Fixed submission:
n = int(input())
a = 1
b = 1
mx = 10 ** 10
while (a <= b and a <= 10**5):
    if n % a == 0:
        b = int(n / a)
        mx = min(mx, max(a, b))
    a += 1
print(len(str(mx)))
Buggy python submission (verdict: Time Limit Exceeded):



N,M,Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]

ans = 0

def check(lst):
    global ans
    tmp = 0
    for i in range(Q):
        a,b,c,d = abcd[i]
        if lst[b-1] == lst[a-1] + c:
            tmp += d
    ans = max(ans, tmp)

def solve(idx, lst):

    if idx >= N:
        check(lst)
        return
    
    if idx <= 0:
        lo = 1
    else:
        lo = lst[idx-1]

    for i in range(lo, M+1):
        
        lst[idx] = i
        solve(idx+1, lst)


lst = [0] * N
for i in range(1, M+1):
    solve(0, lst)
    

print(ans)

Fixed submission:



N,M,Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]

ans = 0

def check(lst):
    global ans
    tmp = 0
    for i in range(Q):
        a,b,c,d = abcd[i]
        if lst[b-1] == lst[a-1] + c:
            tmp += d
    ans = max(ans, tmp)

def solve(idx, lst):

    if idx >= N:
        check(lst)
        return
    
    if idx <= 0:
        lo = 1
    else:
        lo = lst[idx-1]

    for i in range(lo, M+1):
        
        lst[idx] = i
        solve(idx+1, lst)


lst = [0] * N
for i in range(1, M+1):
    solve(0, lst)
    

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


N = int(input())
A = list(map(int, input().split()))
infants = []
for i,a in enumerate(A):
    infants.append((a, i))

infants.sort(reverse=True)
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]


# i番目の幼児まで見るとき
for i in range(N):
    """
    i番目の幼児を配置する方法として、
    ・左側の１～i番目として配置
    ・右側の１～i番目として配置
    の方法がある
    
    左のj人目として配置した場合、右にはi-j人配置されていることになる（右も同じ）
    例：５番目を左の二人目として配置したら、右には残りの３人がいる計算になる

    """
    for j in range(i+1):

        # 左側に配置したとき
        dp[j+1][i-j] =    max(dp[j+1][i-j], dp[j][i-j] + infants[i][0] * abs(infants[i][1] - j))
            
        # 右側に配置したとき
        dp[i-j][j+1] = max(dp[i-j][j+1], dp[i-j][j] + infants[i][0] * abs(infants[i][1] - (N-1 - j)))


ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])

print(ans)


Fixed submission:


N = int(input())
A = list(map(int, input().split()))
infants = []
for i,a in enumerate(A):
    infants.append((a, i))

infants.sort(reverse=True)
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]


# i番目の幼児まで見るとき
for i in range(N):
    """
    i番目の幼児を配置する方法として、
    ・左側の１～i番目として配置
    ・右側の１～i番目として配置
    の方法がある
    
    左のj人目として配置した場合、右にはi-j人配置されていることになる（右も同じ）
    例：５番目を左の二人目として配置したら、右には残りの３人がいる計算になる

    """
    for j in range(i+1):

        # 左側に配置したとき
        dp[j+1][i-j] =    max(dp[j+1][i-j], dp[j][i-j] + infants[i][0] * abs(infants[i][1] - j))
            
        # 右側に配置したとき
        dp[i-j][j+1] = max(dp[i-j][j+1], dp[i-j][j] + infants[i][0] * abs(infants[i][1] - (N-1 - j)))


ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])

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



S = input()
Q = int(input())

order = 1

ans = S
for i in range(Q):
    tfc = list(map(str, input().split()))

    if tfc[0] == "1":
        order *= -1
    else:
        if order == 1:
            if tfc[1] == "1":
                ans = tfc[2] + ans
            else:
                ans = ans + tfc[2]

        else:
            if tfc[1] == "2":
                ans = tfc[2] + ans
            else:
                ans = ans + tfc[2]


if order == 1:
    print(ans)
else:
    print(ans[::-1])

Fixed submission:
from collections import deque



def main():
    S = input()
    Q = int(input())

    order = 1

    ans = deque()
    for i in range(len(S)):
        ans.append(S[i])

    for i in range(Q):
        tfc = list(map(str, input().split()))

        if tfc[0] == "1":
            order *= -1
        else:
            if order == 1:
                if tfc[1] == "1":
                    #ans = tfc[2] + ans
                    ans.appendleft(tfc[2])
                else:
                    #ans = ans + tfc[2]
                    ans.append(tfc[2])

            else:
                if tfc[1] == "2":
                    #ans = tfc[2] + ans
                    ans.appendleft(tfc[2])
                else:
                    #ans = ans + tfc[2]
                    ans.append(tfc[2])


    ans = "".join(ans)

    if order == 1:
        print(ans)
    else:
        print(ans[::-1])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):



S = input()
Q = int(input())

order = 1

ans = S
for i in range(Q):
    tfc = list(map(str, input().split()))

    if tfc[0] == "1":
        order *= -1
    else:
        if order == 1:
            if tfc[1] == "1":
                ans = tfc[2] + ans
            else:
                ans = ans + tfc[2]

        else:
            if tfc[1] == "2":
                ans = tfc[2] + ans
            else:
                ans = ans + tfc[2]


if order == 1:
    print(ans)
else:
    print(ans[::-1])

Fixed submission:
from collections import deque



def main():
    S = input()
    Q = int(input())

    order = 1

    ans = deque()
    for i in range(len(S)):
        ans.append(S[i])

    for i in range(Q):
        tfc = list(map(str, input().split()))

        if tfc[0] == "1":
            order *= -1
        else:
            if order == 1:
                if tfc[1] == "1":
                    #ans = tfc[2] + ans
                    ans.appendleft(tfc[2])
                else:
                    #ans = ans + tfc[2]
                    ans.append(tfc[2])

            else:
                if tfc[1] == "2":
                    #ans = tfc[2] + ans
                    ans.appendleft(tfc[2])
                else:
                    #ans = ans + tfc[2]
                    ans.append(tfc[2])


    ans = "".join(ans)

    if order == 1:
        print(ans)
    else:
        print(ans[::-1])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import math
N = input()
print(math.ceil(N/2))

Fixed submission:
import math
N = int(input())
print(math.ceil(N/2))
Buggy python submission (verdict: Runtime Error):

def main():

    H, N = map(int, input().split())

    ab = [tuple(map(int, input().split())) for _ in range(N)]

    INF = float("inf")
    dp = [[INF for _ in range(H+1)] for _ in range(N+1)]
    dp[0][0] = 0


    for i in range(1, N+1):
        for h in range(H+1):

            tmp = dp[i][h-ab[i-1][0]] if dp[i][h-ab[i-1][0]] != INF else 0
            #if ab[i-1][0] <= h:
            dp[i][h] = min(dp[i-1][h], tmp + ab[i-1][1])

            #else:
            #    dp[i][h] = dp[i-1][h]

            #if i == 3 and h == 9:
            #    print(dp[i][h-ab[i-1][0]], h, ab[i-1][0], tmp, ab[i-1][1] )

    print(dp[-1][H])
    #print(dp)

if __name__ == "__main__":
    main()

Fixed submission:

def main():

    H, N = map(int, input().split())

    ab = [tuple(map(int, input().split())) for _ in range(N)]

    INF = float("inf")
    dp = [[INF for _ in range(H+1)] for _ in range(N+1)]
    dp[0][0] = 0


    for i in range(1, N+1):
        for h in range(H+1):
            aaa = h-ab[i-1][0] if h-ab[i-1][0] >= 0 else 0
            tmp = dp[i][aaa] if dp[i][aaa] != INF else 0
            dp[i][h] = min(dp[i-1][h], tmp + ab[i-1][1])

    print(dp[-1][H])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

N, M = map(int, input().split())

submit = defaultdict(list)
for i in range(M):
    p,s = map(str, input().split())
    submit[p].append(s)


wa = 0
ac = 0
for k in submit.keys():
    for i in range(N):
        if submit[k][i] == "AC":
            wa += i
            ac += 1
            break

print(ac, wa)

Fixed submission:
from collections import defaultdict

N, M = map(int, input().split())

submit = defaultdict(list)
for i in range(M):
    p,s = map(str, input().split())
    submit[p].append(s)


wa = 0
ac = 0
for k in submit.keys():
    if "AC" in submit[k]:
        for i in range(len(submit[k])):
            if submit[k][i] == "WA":
                wa += 1
            elif submit[k][i] == "AC":
                ac += 1
                break
        


print(ac, wa)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)


N = int(input())
C = list(map(int, input().split()))
C.sort()
MOD = 10**9 + 7


ans = 0
# どうも公式ドキュメントによると、組み込み関数のpowの第三引数に値渡すとMODとってくれるらしいので、完全に無駄
def pow_mod(x, n, mod):
    if n == 0:
        return 1 % mod
    elif n % 2 == 0:
        y = pow_mod(x, n//2, mod)
        return y * y % MOD
    else:
        return x * pow_mod(x, n-1, mod) % mod

for i in range(N):
    # 詳細は開設動画の通りだが、i桁目の右にr個の数字、左にlこの数字がある
    l = i
    r = N - i - 1
    # i桁目の寄与が C[i] * 2**l * (2**r + r * 2**(r-1))で、最後に2**Nをかける（Tのとり方が2**Nこあるので）
    # -> C[i] * 2**l * (2**(N+r) + r * 2**(r+N-1))
    ans += ((C[i] * pow_mod(2, l, MOD)) % MOD * (pow_mod(2, N+r, MOD) + r * pow_mod(2, N+r-1, MOD))) % MOD
    ans %= MOD

print(ans)

Fixed submission:
"""



"""

import sys
sys.setrecursionlimit(10**6)


N = int(input())
C = list(map(int, input().split()))
C.sort()
MOD = 10**9 + 7


ans = 0
# どうも公式ドキュメントによると、組み込み関数のpowの第三引数に値渡すとMODとってくれるらしいので、完全に無駄
def pow_mod(x, n, mod):
    if n == 0:
        return 1 % mod
    elif n % 2 == 0:
        y = pow_mod(x, n//2, mod)
        return y * y % MOD
    else:
        return x * pow_mod(x, n-1, mod) % mod

for i in range(N):
    # 詳細は開設動画の通りだが、i桁目の右にr個の数字、左にlこの数字がある
    l = i
    r = N - i - 1
    # i桁目の寄与が C[i] * 2**l * (2**r + r * 2**(r-1))で、最後に2**Nをかける（Tのとり方が2**Nこあるので）
    # -> C[i] * 2**l * (2**(N+r) + r * 2**(r+N-1))
    ans += ((C[i] * pow(2, l, MOD)) % MOD * (pow(2, N+r, MOD) + r * pow(2, N+r-1, MOD))) % MOD
    ans %= MOD

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

"""
AtCoder Beginner Contest 147 D

https://atcoder.jp/contests/abc147/submissions/8876207
https://qiita.com/ZhangChaoran/items/0d59eb5c95cd9414801d


"""

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

# XORではビット毎に計算していくのが基本的な戦略
# 60乗までなので
bits = [0] * 60
for num in A:
    # A_i<2**60なので
    for i in range(60):
        # iビット目に1が立っていたらカウント
        if num & (1<<i):
            bits[i] += 1

"""
pは0からスタート
A_iについて、pビット目に1が立っていたら、i<jを満たすA_jのpビット目に0が立っている個数分2**pをプラスする
また、pビット目に0が立っていたら、i<jを満たすA_jのpビット目に1が立っている個数分2**pをプラスする
i,jのペアを見ていく時に、pビット目の1と0が何回出会うかを考えるとわかりやすいか
配列全体をみて、pビット目に1がa個ある場合、0はN-a個ある。これがΣΣのループで出会うので、
p桁目についてはa*(N-a)回2**pを答えに加えることになる
（a*(N-a)についてはあんまり腑に落ちてないが、例2とかで手を動かしてみるとそうなるので。）

これを全pに対して実施すると良い。
最後にmodを取ると値が大きすぎてあれなので、つどmodを取る
"""



ans = 0
for i, a in enumerate(bits):
    ans += a*(N-a) * 2**i
    ans %= MOD

print(ans)

Fixed submission:

"""
AtCoder Beginner Contest 147 D

https://atcoder.jp/contests/abc147/submissions/8876207
https://qiita.com/ZhangChaoran/items/0d59eb5c95cd9414801d


"""

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

# XORではビット毎に計算していくのが基本的な戦略
# 60乗までなので
bits = [0] * 60
for num in A:
    # A_i<2**60なので
    for i in range(60):
        # iビット目に1が立っていたらカウント
        if num & (1<<i):
            bits[i] += 1

"""
pは0からスタート
A_iについて、pビット目に1が立っていたら、i<jを満たすA_jのpビット目に0が立っている個数分2**pをプラスする
また、pビット目に0が立っていたら、i<jを満たすA_jのpビット目に1が立っている個数分2**pをプラスする
i,jのペアを見ていく時に、pビット目の1と0が何回出会うかを考えるとわかりやすいか
配列全体をみて、pビット目に1がa個ある場合、0はN-a個ある。これがΣΣのループで出会うので、
p桁目についてはa*(N-a)回2**pを答えに加えることになる
（a*(N-a)についてはあんまり腑に落ちてないが、例2とかで手を動かしてみるとそうなるので。）

これを全pに対して実施すると良い。
最後にmodを取ると値が大きすぎてあれなので、つどmodを取る
"""



ans = 0
for i, a in enumerate(bits):
    ans += a*(N-a) * 2**i
    ans %= MOD

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

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

if K >= sum(A):
    print(0)
    exit()

A.sort(reverse=True)
F.sort()

def is_ok(mid):
    cnt = 0
    for i in range(N):
        if A[i] * F[i] <= mid:
            continue
        else:
            cnt += math.ceil((A[i] * F[i] - mid) / F[i]) # A[i]が1減少するごとにF[i]減るのでF[i]で割る  
    
    return cnt <= K

# okは全員がX以下になる最小値に着地するので、A*F<=10**12 なので＋１して最大のケースにも対応する
ok = 10**12 + 1
# 0ではないことが上で保証されてるので、条件を満たさない最大値の0にしておく
ng = 0
while ok - ng > 1:
    
    mid = (ok + ng) // 2
    #print(ok,ng,mid)
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

#print(ok,ng,mid)
print(ok)

Fixed submission:
import math

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

if K >= sum(A):
    print(0)
    exit()

A.sort(reverse=True)
F.sort()

def is_ok(mid):
    cnt = 0
    for i in range(N):
        if A[i] * F[i] <= mid:
            continue
        else:
            cnt += math.ceil((A[i] * F[i] - mid) / F[i]) # A[i]が1減少するごとにF[i]減るのでF[i]で割る  
    
    return cnt <= K

# okは全員がX以下になる最小値に着地するので、A*F<=10**12 なので＋１して最大のケースにも対応する
ok = 10**12 + 1
# 0ではないことが上で保証されてるので、条件を満たさない最大値の0にしておく
ng = 0
while ok - ng > 1:
    
    mid = (ok + ng) // 2
    #print(ok,ng,mid)
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

#print(ok,ng,mid)
print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
from bisect import bisect_right


N = int(input())
L = list(map(int, input().split()))
L.sort()

"""
短いほうから２本固定して条件に合うものをさがす（長いほうから２本固定でもOK）
最長と最短を固定するとややこしくなるから、こういう場合は最長/最短どちらかから固定するほうがいいか
"""


ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        # そもそもcがaやbより大きいので、下の解法のようにilを求める必要などなく、il=で考えれば良かったんや！
        k = bisect_left(L, L[i]+L[j], lo=j)
        ans += k - j - 1



"""
ans = 0
for i in range(N):
    for j in range(i+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]
        #  a < b < c（場合によっては等号を含む）で考えたときの、b - a < cを満たすもの 
        il = bisect_right(L, l, lo=j)
        #  a < b < c（場合によっては等号を含む）で考えたときの、c < a + bを満たすもの
        ir = bisect_left(L, r, lo=j)
        # b - a < cを満たすものがない場合、飛ばす
        if il == N-1:
            break
        
        ans += ir - il - 1
"""

print(ans)


Fixed submission:
from bisect import bisect_left
from bisect import bisect_right


N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]

        il = bisect_right(L, l, j)
        ir = bisect_left(L, r, j)

        if il == N-1:
            break

        ans += ir - il - 1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
from bisect import bisect_right


N = int(input())
L = list(map(int, input().split()))
L.sort()

"""
短いほうから２本固定して条件に合うものをさがす（長いほうから２本固定でもOK）
最長と最短を固定するとややこしくなるから、こういう場合は最長/最短どちらかから固定するほうがいいか
"""


ans = 0
for i in range(N):
    for j in range(i+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]

        #  a < b < c（場合によっては等号を含む）で考えたときの、b - a < cを満たすもの 
        il = bisect_right(L, l, lo=j)
        #  a < b < c（場合によっては等号を含む）で考えたときの、c < a + bを満たすもの
        ir = bisect_left(L, r, lo=j)
        # b - a < cを満たすものがない場合、飛ばす
        if il == N-1:
            break
        
        ans += ir - il - 1

print(ans)


Fixed submission:
from bisect import bisect_left
from bisect import bisect_right


N = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]

        il = bisect_right(L, l, j)
        ir = bisect_left(L, r, j)

        if il == N-1:
            break

        ans += ir - il - 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#from collections import defaultdict 
import copy
A,B = map(int, input().split())

num = min(A,B)
tmps = {}
p = 2
while p <= num:
    if A % p == 0 and B % p == 0:
        tmps[p] = True
    p += 1

#print(tmps)
d = copy.deepcopy(tmps)
for k in tmps.keys():
    if d.get(k, False):
        aaa = copy.deepcopy(d)
        for n in d.keys():
            if k == n:
                continue
            if n > k and n % k == 0:
                aaa.pop(n)
        d = aaa

print(len(d.keys())+1)


Fixed submission:
#from collections import defaultdict 
import copy
import math
A,B = map(int, input().split())

num = min(A,B)
tmps = {}
p = 2
for p in range(2, math.ceil(num**0.5)+1):

    if A % p == 0 and B % p == 0:
        tmps[p] = True

    if A % (num//p) == 0 and B % (num//p) == 0:
        tmps[num//p] = True

    p += 1

if num != 1 and  A % num == 0 and B % num == 0:
    tmps[num] = True


d = copy.deepcopy(tmps)
for k in tmps.keys():

    if d.get(k, False):
        aaa = copy.deepcopy(d)
        for n in d.keys():
            if k == n:
                continue
            if n > k and n % k == 0:
                aaa.pop(n)
        d = aaa

print(len(d.keys())+1)
Buggy python submission (verdict: Time Limit Exceeded):



N,M = map(int, input().split())
ab = []
c = []
for _ in range(M):
    a,b = map(int, input().split())
    ab.append((a,b))
    tmp = tuple(map(int, input().split()))
    bit_c = 0
    # c[i]で開けられる宝箱はbitの１が立っている部分
    for i in tmp:
        bit_c = bit_c | (1 << (i - 1))

    c.append(bit_c)

INF = 10**9
# m番目の鍵をつかって、開けた宝箱がbitの状態になったときの、最小コスト
dp = [INF] * (1 << N)
dp[0] = 0


for bit in range(1 << N):
    for i in range(M):
        dp[bit | c[i]] = min(dp[bit | c[i]], dp[bit] + ab[i][0])

print(dp[-1] if dp[-1] < INF else -1)

Fixed submission:



N,M = map(int, input().split())
ab = []
c = []
for _ in range(M):
    a,b = map(int, input().split())
    ab.append((a,b))
    tmp = tuple(map(int, input().split()))
    bit_c = 0
    # c[i]で開けられる宝箱はbitの１が立っている部分
    for i in tmp:
        bit_c = bit_c | (1 << (i - 1))

    c.append(bit_c)

INF = 10**9
# m番目の鍵をつかって、開けた宝箱がbitの状態になったときの、最小コスト
dp = [INF] * (1 << N)
dp[0] = 0


for bit in range(1 << N):
    for i in range(M):
        dp[bit | c[i]] = min(dp[bit | c[i]], dp[bit] + ab[i][0])

print(dp[-1] if dp[-1] < INF else -1)