Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
ans = 0
T = {'R', 'G', 'B'}
sum_R, sum_G, sum_B = [0], [0], [0]

for i in S:
    sum_R.append(i=='R')
    sum_G.append(i=='G')
    sum_B.append(i=='B')
    
for i in range(1, N+1):
    sum_R[i] = sum_R[i-1] + sum_R[i]
    sum_G[i] = sum_G[i-1] + sum_G[i]
    sum_B[i] = sum_B[i-1] + sum_B[i]
    
dict_RGB = {'R':sum_R, 'G':sum_G, 'B':sum_B}

for i in range(N-2):
    s_i = S[i]
    for j in range(i+1, N-1):
        s_j = S[j]
        if s_i == s_j:
            continue
        
        s_k = list(T - set((s_i, s_j)))[0]
        
        sum_s_k = dict_RGB[s_k]
        ans = ans + sum_s_k[-1] - sum_s_k[j]
        if (2 * j - i < N) and (S[2*j - i]==s_k):
            ans -= 1
        
    
print(ans)

Fixed submission:
N = int(input())
S = input()
ans = 0
T = {'R', 'G', 'B'}
sum_R, sum_G, sum_B = [0], [0], [0]
 
for i in S:
    sum_R.append(i=='R')
    sum_G.append(i=='G')
    sum_B.append(i=='B')
    
for i in range(1, N+1):
    sum_R[i] = sum_R[i-1] + sum_R[i]
    sum_G[i] = sum_G[i-1] + sum_G[i]
    sum_B[i] = sum_B[i-1] + sum_B[i]
    
dict_RGB = {'R':sum_R, 'G':sum_G, 'B':sum_B}
 
for i in range(N-2):
    s_i = S[i]
    for j in range(i+1, N-1):
        s_j = S[j]
        if s_i == s_j:
            continue
        
        s_k = list(T - set((s_i, s_j)))[0]
        
        sum_s_k = dict_RGB[s_k]
        ans = ans + sum_s_k[-1] - sum_s_k[j]
        if (2 * j - i < N) and (S[2*j - i]==s_k):
            ans -= 1
        
    
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
ans = 0
T = {'R', 'G', 'B'}
is_R, is_G, is_B = [], [], []

for i in S:
    is_R.append(i=='R')
    is_G.append(i=='G')
    is_B.append(i=='B')
    
sum_R = [0] + is_R
sum_G = [0] + is_G
sum_B = [0] + is_B

for i in range(1, N+1):
    sum_R[i] = sum_R[i-1] + sum_R[i]
    sum_G[i] = sum_G[i-1] + sum_G[i]
    sum_B[i] = sum_B[i-1] + sum_B[i]
    
dict_RGB = {'R':(is_R, sum_R), 'G':(is_G, sum_G), 'B':(is_B, sum_B)}

for i in range(N-2):
    s_i = S[i]
    for j in range(i+1, N-1):
        s_j = S[j]
        if s_i == s_j:
            continue
        
        s_k = list(T - set((s_i, s_j)))[0]
        
        is_s_k, sum_s_k = dict_RGB[s_k]
        ans = ans + sum_s_k[-1] - sum_s_k[j]
        if (2 * j - i < N) and (is_s_k[2*j - i]):
            ans -= 1
        
    
print(ans)

Fixed submission:
N = int(input())
S = input()
ans = 0
T = {'R', 'G', 'B'}
sum_R, sum_G, sum_B = [0], [0], [0]
 
for i in S:
    sum_R.append(i=='R')
    sum_G.append(i=='G')
    sum_B.append(i=='B')
    
for i in range(1, N+1):
    sum_R[i] = sum_R[i-1] + sum_R[i]
    sum_G[i] = sum_G[i-1] + sum_G[i]
    sum_B[i] = sum_B[i-1] + sum_B[i]
    
dict_RGB = {'R':sum_R, 'G':sum_G, 'B':sum_B}
 
for i in range(N-2):
    s_i = S[i]
    for j in range(i+1, N-1):
        s_j = S[j]
        if s_i == s_j:
            continue
        
        s_k = list(T - set((s_i, s_j)))[0]
        
        sum_s_k = dict_RGB[s_k]
        ans = ans + sum_s_k[-1] - sum_s_k[j]
        if (2 * j - i < N) and (S[2*j - i]==s_k):
            ans -= 1
        
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np


N, X, Y = map(int, input().split())
X, Y = X-1, Y-1
d = np.zeros((N, N))

for i in range(N-1):
    for j in range(i+1, N):
        d[i, j] = min(j-i, abs(X-i)+1+abs(Y-j))

for k in range(1, N):
    print(np.sum(d==k))

Fixed submission:
N, X, Y = map(int, input().split())
X, Y = X-1, Y-1
ans = {i:0 for i in range(1, N)}

for i in range(N-1):
    for j in range(i+1, N):
        d = min(j-i, abs(X-i)+1+abs(Y-j))
        ans[d] += 1
        
for _, v in ans.items():
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np


N, X, Y = map(int, input().split())
X, Y = X-1, Y-1
d = np.zeros((N, N))

for i in range(N-1):
    for j in range(i+1, N):
        if i >= Y or j <= X:
            d[i, j] = j-i
            continue
        d[i, j] = min(j-i, abs(X-i)+1+abs(Y-j))

for k in range(1, N):
    print(np.sum(d==k))

Fixed submission:
N, X, Y = map(int, input().split())
X, Y = X-1, Y-1
ans = {i:0 for i in range(1, N)}

for i in range(N-1):
    for j in range(i+1, N):
        d = min(j-i, abs(X-i)+1+abs(Y-j))
        ans[d] += 1
        
for _, v in ans.items():
    print(v)
Buggy python submission (verdict: Runtime Error):
s = input()
n = len(s)
 
a = s == reversed(a)
s1 = s[:(n-1)//2]
b = s1 == s1[::-1]
s2 = s[(n+3)//2 + 1:]
c = s2 == s2[::-1]
 
print(['No', 'Yes'][a and b and c])

Fixed submission:
s = input()
n = len(s)
 
a = s == s[::-1]
s1 = s[:(n-1)//2]
b = s1 == s1[::-1]
s2 = s[(n+3)//2 - 1:]
c = s2 == s2[::-1]
 
print(['No', 'Yes'][a and b and c])

Buggy python submission (verdict: Runtime Error):
s = input()
n = len(s)

a = s == reversed(a)
s1 = s[:(n-1)//2]
b = s1 == reversed(s1)
s2 = s[(n+3)//2 + 1:]
c = s2 == reversed(s2)

print(['No', 'Yes'][a and b and c])

Fixed submission:
s = input()
n = len(s)
 
a = s == s[::-1]
s1 = s[:(n-1)//2]
b = s1 == s1[::-1]
s2 = s[(n+3)//2 - 1:]
c = s2 == s2[::-1]
 
print(['No', 'Yes'][a and b and c])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


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

for k in range(N):
    c_a = count_A.copy()
    c_a[A[k]] -= 1
    ans = 0
    for v in c_a.values():
        ans += v*(v-1)//2
    print(ans)

Fixed submission:
from collections import Counter


N = int(input())
A = list(map(int, input().split()))
count_A = Counter(A)
sum_A = sum([i*(i-1)//2 for i in count_A.values()])

for k in range(N):
    n = count_A[A[k]]
    ans = sum_A - n + 1
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
import numpy as np


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

for k in range(N):
    c_a = count_A.copy()
    c_a[A[k]] -= 1
    a = np.array(list(c_a.values())).reshape(-1,)
    b = a-1
    print(np.dot(b, a) // 2)

Fixed submission:
from collections import Counter


N = int(input())
A = list(map(int, input().split()))
count_A = Counter(A)
sum_A = sum([i*(i-1)//2 for i in count_A.values()])

for k in range(N):
    n = count_A[A[k]]
    ans = sum_A - n + 1
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = [i for i in input()]
Q = int(input())
 
f = 0
 
for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if f+int(F) % 2 == 1:
        s = [c] + s
    else:
        s = s + [c]
        
if f:
    print(''.join(s[::-1]))
else:
    print(''.join(s))

Fixed submission:
from queue import deque
s = deque([i for i in input()])
Q = int(input())
 
f = 0
 
for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if f+int(F) % 2 == 1:
        s.appendleft(c)
    else:
        s.append(c)
        
if f:
    print(''.join(reversed(s)))
else:
    print(''.join(s))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
Q = int(input())
 
f = 0
 
for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if f+int(F) % 2 == 1:
        s = c + s
    else:
        s = s + c
        
if f:
    print(s[::-1])
else:
    print(s)

Fixed submission:
from queue import deque
s = deque([i for i in input()])
Q = int(input())
 
f = 0
 
for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if f+int(F) % 2 == 1:
        s.appendleft(c)
    else:
        s.append(c)
        
if f:
    print(''.join(reversed(s)))
else:
    print(''.join(s))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
Q = int(input())

f = 0

for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if f+int(F) % 2 == 1:
        s = c + s
    else:
        s = s + c
        
if f:
    print(s[::-1])
else:
    print(s)

Fixed submission:
from queue import deque
s = deque([i for i in input()])
Q = int(input())
 
f = 0
 
for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if f+int(F) % 2 == 1:
        s.appendleft(c)
    else:
        s.append(c)
        
if f:
    print(''.join(reversed(s)))
else:
    print(''.join(s))

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
Q = int(input())

def add_head(s, c):
    return c + s

def add_tail(s, c):
    return s + c

f = 0

for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if (f == 0 and int(F) == 1) or (f == 1 and int(F) == 2):
        s = c + s
    elif (f == 1 and int(F) == 1) or (f == 0 and int(F) == 2):
        s = s + c
        
if f:
    print(s[::-1])
else:
    print(s)

Fixed submission:
from queue import deque
s = deque([i for i in input()])
Q = int(input())
 
f = 0
 
for _ in range(Q):
    q = input()
    if int(q[0]) == 1:
        f = abs(f-1)
        continue
    
    _, F, c = q.split()
    if f+int(F) % 2 == 1:
        s.appendleft(c)
    else:
        s.append(c)
        
if f:
    print(''.join(reversed(s)))
else:
    print(''.join(s))
Buggy python submission (verdict: Runtime Error):
import numpy as np


A = np.array([list(map(int, input().split())) for _ in range(3)])
n = int(input())
for _ in range(n):
  b = int(input())
  A = np.where(A == b, 0, A)
  
x = np.all(A[[0, 1, 2], [0, 1, 2]] == 0)
y = np.all(A[[0, 1, 2], [2, 1, 0]] == 0)
z = np.any(np.sum(A, axis=0) == 0)
w = np.any(np.sum(A, axis=1) == 0)

print(['Yes', 'No'][!x and !y and !z and !w])

Fixed submission:
import numpy as np
 

A = np.array([list(map(int, input().split())) for _ in range(3)])
n = int(input())
for _ in range(n):
  b = int(input())
  A = np.where(A == b, 0, A)
  
x = np.all(A[[0, 1, 2], [0, 1, 2]] == 0)
y = np.all(A[[0, 1, 2], [2, 1, 0]] == 0)
z = np.any(np.sum(A, axis=0) == 0)
w = np.any(np.sum(A, axis=1) == 0)
 
print(['Yes', 'No'][not x and not y and not z and not w])
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
S, C = [], []
ans = -1

for _ in range(m):
  s, c = map(int, input().split())
  S.append(s)
  C.append(c)
  
for num in range(10 ** (max(S) - 1), 10 ** n):
  num = str(num)
  f = 1
  for s, c in zip(S, C):
    s = s - 1
    if int(num[s]) != c:
      f = 0
      break
      
  if f:
    ans = num
    break
    
print(ans)

Fixed submission:
n, m = map(int, input().split())
 
num = [-1] * n
ans = -1
f = 1
 
for _ in range(m):
  s, c = map(int, input().split())
  if s == 1 and c == 0:
    if n == 1:
      ans = 0
    f = 0
    break
    
  i = num[s - 1]
  if i == -1:
    num[s-1] = c
  elif i == c:
    continue
  else:
    f = 0
    break
  
if num[0] == -1:
  if n == 1:
    num[0] = 0
  else:
    num[0] = 1
  
if f:
  num = [0 if n == -1 else n for n in num]
  ans = ''.join(map(str, num))
  
print(ans)

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
S, C = [], []
for _ in range(m):
  s, c = map(int, input().split())
  S.append(s)
  C.append(c)
  
for num in range(10 ** (max(S) - 1), 10 ** n):
  num = str(num)
  f = 1
  for s, c in zip(S, C):
    s = s - 1
    if int(num[s]) != c:
      f = 0
      break
      
  if f:
    ans = num
    break
    
print(ans)

Fixed submission:
n, m = map(int, input().split())
 
num = [-1] * n
ans = -1
f = 1
 
for _ in range(m):
  s, c = map(int, input().split())
  if s == 1 and c == 0:
    if n == 1:
      ans = 0
    f = 0
    break
    
  i = num[s - 1]
  if i == -1:
    num[s-1] = c
  elif i == c:
    continue
  else:
    f = 0
    break
  
if num[0] == -1:
  if n == 1:
    num[0] = 0
  else:
    num[0] = 1
  
if f:
  num = [0 if n == -1 else n for n in num]
  ans = ''.join(map(str, num))
  
print(ans)

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
S, C = []
for _ in range(m):
  s, c = map(int, input().split())
  S.append(s)
  C.append(c)
  
for num in range(10 ** (max(S) - 1), 10 ** n):
  num = str(num)
  f = 1
  for s, c in zip(S, C):
    s = s - 1
    if int(num[s]) != c:
      f = 0
      break
      
  if f:
    ans = num
    break
    
print(ans)

Fixed submission:
n, m = map(int, input().split())
 
num = [-1] * n
ans = -1
f = 1
 
for _ in range(m):
  s, c = map(int, input().split())
  if s == 1 and c == 0:
    if n == 1:
      ans = 0
    f = 0
    break
    
  i = num[s - 1]
  if i == -1:
    num[s-1] = c
  elif i == c:
    continue
  else:
    f = 0
    break
  
if num[0] == -1:
  if n == 1:
    num[0] = 0
  else:
    num[0] = 1
  
if f:
  num = [0 if n == -1 else n for n in num]
  ans = ''.join(map(str, num))
  
print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())

def calculate_Expectation(n):
    n = int(n)
    p = 1/n
    e = p * (n*(n+1)/2)
    return e

E = list(map(calculate_Expectation, input().split()))
S = [0]
for i, e in enumerate(E):
    S.append(S[i]+e)

sum_of_E = []
for left in range(1, N+1-K):
    right = left + K
    sum_of_E.append(S[right]-S[left])
print(max(sum_of_E))

Fixed submission:
N, K = map(int, input().split())

def calculate_Expectation(n):
    n = int(n)
    p = 1/n
    e = p * (n*(n+1)/2)
    return e

E = list(map(calculate_Expectation, input().split()))
if N == K:
    print(sum(E))
else:
    S = [0]
    for i, e in enumerate(E):
        S.append(S[i]+e)

    sum_of_E = []
    for left in range(1, N+1-K):
        right = left + K
        sum_of_E.append(S[right]-S[left])
    print(max(sum_of_E))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
P = list(map(int, input().split()))
min_n = [min(P[:i]) for i in range(1, n+1)]
c = 0
for i in range(n):
    if P[i] == min_n[i]:
        c += 1
        
print(c)

Fixed submission:
n = int(input())
P = list(map(int, input().split()))
c = 1
minimum = P.pop(0)
if minimum != 1:
    for p in P:
        if p <= minimum:
            c += 1
            minimum = p
        if p == 1:
            break
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
idx = 0
cnt = 0
for n in range(N):
    if A[idx] == idx+1:
        idx += 1
    else:
        A.pop(idx)
        cnt += 1
 
if cnt == N:
    print(-1)
else:
    print(cnt)

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

i = 1
ans = 0
for n in range(N):
  if i == A[n]:
    i += 1
  else:
    ans += 1
if ans == N:
  ans = -1
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
idx = [0]
for n in range(1, N+1):
    try:
        idx.append(A[sum(idx):].index(n))
    except:
        idx.append(len(A[sum(idx):]))
        break
if N == A[0] == 1:
    print(0)
elif (N == 1 and A[0] != 1) or (len(idx) == 2):
    print(-1)
else:
    print(sum(idx)-len(idx)+2)

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

i = 1
ans = 0
for n in range(N):
  if i == A[n]:
    i += 1
  else:
    ans += 1
if ans == N:
  ans = -1
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
idx = [0]
for n in range(1, N+1):
    try:
        idx.append(A[idx[-1]:].index(n) + len(A[:idx[-1]]))
    except:
        break
idx.append(N-1)
if len(idx) == 2:
    print(-1)
else:
    a = [i-j for i,j in zip(idx[1:], idx[:-1])]
    print(sum(a)-(len(idx)-2)+1)

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

i = 1
ans = 0
for n in range(N):
  if i == A[n]:
    i += 1
  else:
    ans += 1
if ans == N:
  ans = -1
  
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
idx = 0
cnt = 0
for n in range(N):
    if A[idx] == idx+1:
        idx += 1
    else:
        A.pop(idx)
        cnt += 1

if cnt == N:
    print(-1)
else:
    print(cnt)

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

i = 1
ans = 0
for n in range(N):
  if i == A[n]:
    i += 1
  else:
    ans += 1
if ans == N:
  ans = -1
  
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    ans = []
    AB = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        AB[a].append(b)
        AB[b].append(a)
    
    M = max([len(i) for i in AB])
    _c = set(range(1, M+1))
    C = [_c for _ in range(N+1)]

    root = 1
    checked = set()
    q = [root]

    while q:
        i = q.pop(0)
        if i in checked:
            continue
        checked.add(i)
        for j in AB[i]:
            if j in checked:
                continue
            k = C[i].pop()
            ans.append(k)
            C[j] = C[j] - set([k])
            q.append(j)

    print(M)   
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Fixed submission:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(readline())
graph = [[] for _ in range(N+1)]
AB = []

for _ in range(N-1):
    a, b = map(int, readline().split())
    AB.append((a, b))
    graph[a].append(b)
    graph[b].append(a)

parent = [0] * (N+1)
root = 1
stack = [root]
color = [0] * (N+1)
while stack:
    x = stack.pop()
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        parent[y] = x
        color[y] = c
        c += 1
        stack.append(y)

print(max(color))

for a, b in AB:
    if parent[a] == b:
        print(color[a])
    else:
        print(color[b])
Buggy python submission (verdict: Runtime Error):
import math

x, y = map(int, input().split())
mod = 10 ** 9 + 7
a = (2 * y - x) / 3
b = (2 * x - y) / 3

if (not a.is_integer()) or (not b.is_integer()):
    print(0)
else:
    a, b = int(a), int(b)
    I = [1] * (a + b + 1)
    for n in range(1, a+b+1):
        I[n] = I[n-1] * n
        I[n] %= mod
    i, j, k = I[a+b], I[a], I[b]
    j = pow(j, mod-2, mod)
    k = pow(k, mod-2, mod)

    ans = i * j * k
    ans %= mod
    print(ans)

Fixed submission:
import math

x, y = map(int, input().split())
mod = 10 ** 9 + 7
a = (2 * y - x) / 3
b = (2 * x - y) / 3

if (not a.is_integer()) or (not b.is_integer()) or \
    (a < 0) or (b < 0):
    print(0)
else:
    a, b = int(a), int(b)
    I = [1] * (a + b + 1)
    for n in range(1, a+b+1):
        I[n] = I[n-1] * n
        I[n] %= mod
    i, j, k = I[a+b], I[a], I[b]
    j = pow(j, mod-2, mod)
    k = pow(k, mod-2, mod)

    ans = i * j * k
    ans %= mod
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = sorted(map(int, input().split()), reverse=True)
cnt = 0

for i in range(N - 2):
    c = L[i]
    
    for j in range(i + 1, N - 1):
        b = L[j]
        l = j
        r = N - 1
        
        while True:
            idx = -(-(l + r) // 2)
            
            if L[idx] > abs(b - c):
                if l == idx:
                    break
                l = idx
            else:
                if r == idx:
                    break
                r = idx
                
        cnt += l - j
        
print(cnt)

Fixed submission:
N = int(input())
L = sorted(map(int, input().split()), reverse=True)
cnt = 0

for i in range(N - 2):
    c = L[i]
    
    for j in range(i + 1, N - 1):
        b = L[j]
        l = j
        r = N - 1
        
        while True:
            idx = -(-(l + r) // 2)
            
            if L[idx] > c - b:
                if l == idx:
                    break
                l = idx
            else:
                if r == idx:
                    break
                r = idx
                
        cnt += l - j
        
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int, input().split()))
cnt = 0
for i in range(0, N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        for k in range(j+1, N):
            c = L[k]
            if a >= b + c or b >= c + a or c >= a + b:
                cnt += 1
                continue
                
print(N * (N - 1) * (N - 2) //  6 - cnt)

Fixed submission:
N = int(input())
L = sorted(map(int, input().split()), reverse=True)
cnt = 0

for i in range(N - 2):
    c = L[i]
    
    for j in range(i + 1, N - 1):
        b = L[j]
        l = j
        r = N - 1
        
        while True:
            idx = -(-(l + r) // 2)
            
            if L[idx] > c - b:
                if l == idx:
                    break
                l = idx
            else:
                if r == idx:
                    break
                r = idx
                
        cnt += l - j
        
print(cnt)
Buggy python submission (verdict: Runtime Error):
S = input()
S_odd = [s for i, s in enumerate(S) if i % 2 == 0]
S_even = [s for i, s in enumerate(S) if i % 2 != 0]

for i in S_odd:
    if i in ['R', 'U', 'D']:
        f = 1
    else:
        f = 0
        break
for j in S_even:
    if j in ['L', 'U', 'D']:
        g = 1
    else:
        g = 0
        break
if f*g:
    print('Yes')
else:
    print('No')
        

Fixed submission:
S = input()
S1 = S[::2]
S2 = S[1::2]
f = 1
for i in S1:
    if i in ['R', 'U', 'D']:
        f *= 1
    else:
        f *= 0
        
for i in S2:
    if i in ['L', 'U', 'D']:
        f *= 1
    else:
        f *= 0
if f:
    print('Yes')
else:
    print('No')

Buggy python submission (verdict: Runtime Error):
S = input()
S_odd = [s for i, s in enumerate(S) if i % 2 == 0]
S_even = [s for i, s in enumerate(S) if i % 2 != 0]

for i in S_odd:
    if i in ['R', 'U', 'D']:
        f = 1
    else:
        f = 0
        break
for j in S_even:
    if j in ['L', 'U', 'D']:
        g = 1
    else:
        g = 0
        break
if f*g:
    print('Yes')
else:
    print('No')
        

Fixed submission:
S = input()
S1 = S[::2]
S2 = S[1::2]
f = 1
for i in S1:
    if i in ['R', 'U', 'D']:
        f *= 1
    else:
        f *= 0
        
for i in S2:
    if i in ['L', 'U', 'D']:
        f *= 1
    else:
        f *= 0
if f:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
q = []
for a in A:
    heapq.heappush(q, -a)
    
for _ in range(M):
    tmp = -heapq.heappop(q)
    heapq.heappush(q, -(tmp//2))
print(-sum(q))

Fixed submission:
import heapq

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
q = []
for a in A:
    heapq.heappush(q, -a)
    
for _ in range(M):
    tmp = -heapq.heappop(q)
    heapq.heappush(q, -(tmp//2))
print(-sum(q))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
A = sorted(A)
for _ in range(M):
    A[-1] = int(A[-1] * 0.5)
    A = sorted(A)
print(sum(A))

Fixed submission:
import heapq

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
q = []
for a in A:
    heapq.heappush(q, -a)
    
for _ in range(M):
    tmp = -heapq.heappop(q)
    heapq.heappush(q, -(tmp//2))
print(-sum(q))
Buggy python submission (verdict: Runtime Error):
n = int(input)
print(n*(n-1)//2)

Fixed submission:
N = int(input())

if N % 2 == 0:
    print((N-1)*N//2)
else:
    print(N*(N-1)//2)

Buggy python submission (verdict: Time Limit Exceeded):
print(sum([i for i in range(1, int(input()))]))

Fixed submission:
N = int(input())

if N % 2 == 0:
    print((N-1)*N//2)
else:
    print(N*(N-1)//2)