Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P_list = list(map(int, input().split()))

count = 0

for j in range(N):
    target = P_list[j]
    if min(P_list[:j+1]) >= target:
        count += 1

print(count)

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

count = 1
temp = P_list[0]

for j in range(1, N):
    if P_list[j] == min(P_list[j], temp):
        count += 1
        temp = P_list[j]

print(count)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L_list = list(map(int, input().split()))

L_list = sorted(L_list)

count = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if L_list[i] + L_list[j] > L_list[k]:
                count += 1
            else:
                break

print(count)

Fixed submission:
import bisect

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

L_list = sorted(L_list)

total = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        total += bisect.bisect_left(L_list, L_list[i] + L_list[j]) - j -1

print(total)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L_list = list(map(int, input().split()))

L_list = sorted(L_list)

count = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            count += L_list[i] + L_list[j] > L_list[k]

print(count)

Fixed submission:
import bisect

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

L_list = sorted(L_list)

total = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        total += bisect.bisect_left(L_list, L_list[i] + L_list[j]) - j -1

print(total)

Buggy python submission (verdict: Runtime Error):
N = int(input())
L_list = list(map(int, input().split()))

L_list = sorted(L_list)

count = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            count += L_list[i] + L_list[j] > L_list[k]:

print(count)

Fixed submission:
import bisect

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

L_list = sorted(L_list)

total = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        total += bisect.bisect_left(L_list, L_list[i] + L_list[j]) - j -1

print(total)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L_list = list(map(int, input().split()))

L_list = sorted(L_list)

count = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if L_list[i] + L_list[j] > L_list[k]:
                count += 1
            else:
                break
            
print(count)

Fixed submission:
import bisect

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

L_list = sorted(L_list)

total = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        total += bisect.bisect_left(L_list, L_list[i] + L_list[j]) - j -1

print(total)
Buggy python submission (verdict: Runtime Error):
import numpy as np

def count_sequence_one(x_array):
    """arrayに存在する連続する1の個数を数える
    """
    x_array = np.append(0, x_array)
    x_array = np.append(x_array, 0)

    temp = np.arange(len(x_array))
    temp[x_array > 0] = 0
    np.maximum.accumulate(temp, out=temp)
    left = temp

    x_array_reversed = x_array[::-1]
    temp = np.arange(len(x_array))
    temp[x_array_reversed > 0] = 0
    np.maximum.accumulate(temp, out=temp)
    right = len(x_array) - 1 - temp[::-1]

    y_array = right
    y_array -= left + 1
    y_array[x_array == 0] = 0

    y_array =  y_array[1:len(y_array)-1]

    return y_array


if __name__ == "__main__":

    N = int(input())
    H_array = np.array(list(map(int, input().split())))

    can_move = H_array[1:] <= H_array[:-1]
    x = count_sequence_one(can_move)
    
    print(x.max())

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

max_count = 0
count = 0
for i in range(1, N):
    if H[i-1] >= H[i]:
        count += 1
    else:
        max_count = max(max_count, count)
        count = 0
        
max_count = max(max_count, count)
print(max_count)

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

N = int(input())
H_array = np.array(list(map(int, input().split())))

can_move = H_array[1:] <= H_array[:-1]

max_series = 0
for i in range(N-1):
    temp_sum = 0
    for j in range(i, N-1):
        if not can_move[j]:
            max_series = max(max_series, temp_sum)
            break
        temp_sum += 1
        max_series = max(max_series, temp_sum)

print(max_series)

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

max_count = 0
count = 0
for i in range(1, N):
    if H[i-1] >= H[i]:
        count += 1
    else:
        max_count = max(max_count, count)
        count = 0
        
max_count = max(max_count, count)
print(max_count)
Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())

temp = np.linspace(1, N-1, N-1)
answer = np.cumsum(temp)

print(int(answer[-1]))

Fixed submission:
N = int(input())

answer = N * (N - 1) // 2

print(int(answer))

Buggy python submission (verdict: Runtime Error):
import numpy as np

N = int(input())

temp = np.linspace(1, N, N)
re_temp = np.linspace(2, N, N-1)
re_temp = np.append(re_temp, 1)

answer = (temp % re_temp).sum()
print(int(answer))


Fixed submission:
N = int(input())

answer = N * (N - 1) // 2

print(int(answer))
Buggy python submission (verdict: Time Limit Exceeded):
import collections

def check_equal(a_dict, b_dict):
    result = True
    for k_a, v_a in a_dict.items():
        if k_a not in b_dict:
            result = False
            break
        if a_dict[k_a] != b_dict[k_a]:
            result = False
            break
    
    return result


if __name__ == "__main__":    
    N = int(input())
    count_list = []

    for i in range(N):
        sentence = input()
        c = dict(collections.Counter(sentence))
        count_list.append(c)

    total = 0
    for i in range(N):
        for j in range(i+1, N):
            total += check_equal(count_list[i], count_list[j])

    print(total)

Fixed submission:
N = int(input())

sentence_count_dict = {}
for _ in range(N):
    sentence = list(input())
    sentence = ''.join(sorted(sentence))
    if sentence in sentence_count_dict:
        sentence_count_dict[sentence] += 1
    else:
        sentence_count_dict[sentence] = 1

total = 0
for v in sentence_count_dict.values():
    total += (v * (v-1)) / 2

print(int(total))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]
dp = [-1] * N

ans = 0
for i in range(N):
    for j in range(N):
        if A[i] > dp[j]:
            dp[j] = A[i]
            ans = max(ans, j+1)
            break

print(ans)

Fixed submission:
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]
dp = [-1] * N
dp[N-1] = A[0]

ans = 0
for i in range(1, N):
    target_index = bisect.bisect_left(dp, A[i])
    dp[target_index-1] = A[i]

print(N - dp.count(-1))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]
dp = [-1] * N

ans = 0
for i in range(N):
    for j in range(N):
        if A[i] > dp[j]:
            dp[j] = A[i]
            ans = max(ans, j+1)
            break

print(ans)

Fixed submission:
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]
dp = [-1] * N
dp[N-1] = A[0]

ans = 0
for i in range(1, N):
    target_index = bisect.bisect_left(dp, A[i])
    dp[target_index-1] = A[i]

print(N - dp.count(-1))

Buggy python submission (verdict: Time Limit Exceeded):
WIDE = 10**5 + 10

N = int(input())
A = [int(input()) for _ in range(N)]

dp = [[-1] for _ in range(WIDE)]

for i in range(N):
    for j in range(len(dp)):
        if dp[j][-1] < A[i]:
            dp[j].append(A[i])
            break

count = 0
for i in range(WIDE):
    if len(dp[i]) >= 2:
        count += 1
    if len(dp[i]) == 1:
        break       

print(count)

Fixed submission:
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]
dp = [-1] * N
dp[N-1] = A[0]

ans = 0
for i in range(1, N):
    target_index = bisect.bisect_left(dp, A[i])
    dp[target_index-1] = A[i]

print(N - dp.count(-1))

Buggy python submission (verdict: Time Limit Exceeded):
WIDE = 10**5 + 10

N = int(input())
A = [int(input()) for _ in range(N)]

dp = [[-1] for _ in range(WIDE)]

for i in range(N):
    for j in range(len(dp)):
        if dp[j][-1] < A[i]:
            dp[j].append(A[i])
            break

count = 0
for i in range(WIDE):
    if len(dp[i]) >= 2:
        count += 1
    if len(dp[i]) == 1:
        break       

print(count)

Fixed submission:
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]
dp = [-1] * N
dp[N-1] = A[0]

ans = 0
for i in range(1, N):
    target_index = bisect.bisect_left(dp, A[i])
    dp[target_index-1] = A[i]

print(N - dp.count(-1))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(M)]

count_dict = {}

gate = set(range(10**5 + 1))

for i in range (M):
    l = LR[i][0]
    r = LR[i][1]
    temp = set(range(l, r+1))

    gate = gate & temp

print(len(gate))


Fixed submission:
N, M = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(M)]

count_dict = {}

gate = set(range(10**5 + 1))

L = 1
R = 10**5

for i in range (M):
    l = LR[i][0]
    r = LR[i][1]

    if l > L:
        L = l
    if r < R:
        R = r

print(len(range(L, R+1)))

Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(M)]

count_dict = {}

for i in range (M):
    l = LR[i][0]
    r = LR[i][1]

    for j in range(l, r+1):
        if j in count_dict:
            count_dict[j] += 1
        else:
            count_dict[j] = 1

total = 0
for i in count_dict.values():
    if i == M:
        total += 1

print(total)

Fixed submission:
N, M = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(M)]

count_dict = {}

gate = set(range(10**5 + 1))

L = 1
R = 10**5

for i in range (M):
    l = LR[i][0]
    r = LR[i][1]

    if l > L:
        L = l
    if r < R:
        R = r

print(len(range(L, R+1)))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [float('inf')] * (N)
dp[0] = 0

for i in range(1, N):
    min_from = max(0, i - K)

    temp = float('inf')
    for j in range(min_from, i):
        temp = min(temp, dp[j] + abs(H[i] - H[j]))
    dp[i] =temp

print(dp[N-1])

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

dp = [float('inf')] * (N)
dp[0] = 0

for i in range(1, N):
    min_from = max(0, i - K)

    temp = float('inf')
    for j in range(min_from, i):
        temp = min(temp, dp[j] + abs(H[i] - H[j]))
    dp[i] =temp

print(dp[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
s = [''] + s
t = list(input())
t = [''] + t
dp = [[0] * (len(t)) for _ in range(len(s))]

# dpテーブル作成

for i in range(1, len(s)):
    for j in range(1, len(t)):

        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 

answer_len = dp[len(s)-1][len(t)-1]

# dpテーブル逆走
answer = [0] * answer_len
i = len(s) -1
j = len(t) -1

while True:
    if dp[i][j] - dp[i-1][j-1] == 1 and dp[i][j] - dp[i][j-1] == 1 and dp[i][j] - dp[i-1][j] == 1:
        answer[answer_len-1] = s[i]
        answer_len -= 1
        i -= 1
        j -= 1
        if answer[0] != 0:
            break
    elif dp[i][j] - dp[i][j-1] == 1 and dp[i][j] - dp[i-1][j] != 1:
        i -= 1
    elif dp[i][j] - dp[i][j-1] != 1 and dp[i][j] - dp[i-1][j] == 1:
        j -= 1
    else:
        j -= 1

    if j == 0:
        j += 1
        i -= 1
    
    if i == 0:
        break
 
print(''.join(answer))

Fixed submission:
s = list(input())
s = [''] + s
t = list(input())
t = [''] + t
dp = [[0] * (len(t)) for _ in range(len(s))]

# dpテーブル作成

for i in range(1, len(s)):
    for j in range(1, len(t)):

        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 

answer_len = dp[len(s)-1][len(t)-1]

# dpテーブル逆走
answer = [0] * answer_len
i = len(s) -1
j = len(t) -1

while True:
    if dp[i][j] - dp[i-1][j-1] == 1 and dp[i][j] - dp[i][j-1] == 1 and dp[i][j] - dp[i-1][j] == 1:
        answer[answer_len-1] = s[i]
        answer_len -= 1
        i -= 1
        j -= 1
        if answer[0] != 0:
            break
    elif dp[i][j] - dp[i][j-1] == 1 and dp[i][j] - dp[i-1][j] != 1:
        i -= 1
    elif dp[i][j] - dp[i][j-1] != 1 and dp[i][j] - dp[i-1][j] == 1:
        j -= 1
    else:
        j -= 1

    if j == 0:
        j += 1
        i -= 1
    
    if i == 0:
        break
 
print(''.join(answer))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(float, input().split()))
P = [0] + P
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 1

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

for i in range(1, N+1):
    for j in range(1, i+1):
        dp[i][j] += dp[i-1][j-1] * P[i] + dp[i-1][j] * (1 - P[i]) 

ans = 0
if N % 2 == 0:
    start = N // 2
else:
    start = N // 2 + 1

for i in range(start, N+1):
    ans += dp[N][i]
    
print(ans)

Fixed submission:
N = int(input())
P = list(map(float, input().split()))
P = [0] + P
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 1

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

for i in range(1, N+1):
    for j in range(1, i+1):
        dp[i][j] += dp[i-1][j-1] * P[i] + dp[i-1][j] * (1 - P[i]) 

ans = 0
if N % 2 == 0:
    start = N // 2
else:
    start = N // 2 + 1

for i in range(start, N+1):
    ans += dp[N][i]
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
dp = [False] * (K+1)

for i in range(K+1):
    for j in range(N):
        if i - A[j] >= 0 :
            dp[i] = dp[i] | (not dp[i-A[j]])

if dp[K]:
    print('First')
else:
    print('Second')


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
dp = [False] * (K+1)

for i in range(K+1):
    for j in range(N):
        if i - A[j] >= 0 :
            dp[i] = dp[i] | (not dp[i-A[j]])

if dp[K]:
    print('First')
else:
    print('Second')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
dp = [[0] * (N+1) for _ in range(N+1)]

for width in range(1, N+1):
    for i in range(N-width+1):
        j = i + width

        if (N - width) % 2 == 0:
            dp[i][j] = max(dp[i+1][j] + A[i], dp[i][j-1] + A[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - A[i], dp[i][j-1] - A[j-1])

print(dp[0][N])

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
dp = [[0] * (N+1) for _ in range(N+1)]

for width in range(1, N+1):
    for i in range(N-width+1):
        j = i + width

        if (N - width) % 2 == 0:
            dp[i][j] = max(dp[i+1][j] + A[i], dp[i][j-1] + A[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - A[i], dp[i][j-1] - A[j-1])

print(dp[0][N])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
INF = 10**10
cost = [[INF]*N for _ in range(N)] # INFで初期化v

for u in range(N):
    C = list(map(int, input().split()))
    for v in range(N):
        if u==v: # 自身への道路はINFのままにする
            continue
        cost[u][v] = C[v]
 
ans = 0
for u in range(N):
    for v in range(u+1,N): # u < v
        mn = INF # u-w-vのような経路の中で最小の距離を求める
        for w in range(N):
            mn = min(mn, cost[u][w]+cost[w][v])    
        if (cost[u][v] > mn): # 与えられた行列が最短経路ではない
            print (-1) # 終了して良い
            exit()
        elif (cost[u][v] < mn): # 等しくない場合はu-vを直接結ぶ道路が必要 
            ans += cost[u][v]                      
print (ans)

Fixed submission:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
INF = float('inf')

for i in range(N):
    A[i][i] = INF

answer = 0
for i in range(N):
    for j in range(i+1, N):
  
        count = INF
        for k in range(N):   
            count = min(count, A[i][k] + A[k][j])
        
        if A[i][j] > count:
            print(-1)
            exit()

        if A[i][j] < count:
            answer += A[i][j]
        
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
INF = float('inf')

for i in range(N):
    A[i][i] = INF

answer = 0
for i in range(N):
    for j in range(i+1, N):
  
        count = INF
        for k in range(N):   
            count = min(count, A[i][k] + A[k][j])
        
        if A[i][j] > count:
            print(-1)
            exit()

        if A[i][j] < count:
            answer += A[i][j]
        
print(answer)

Fixed submission:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
INF = float('inf')

for i in range(N):
    A[i][i] = INF

answer = 0
for i in range(N):
    for j in range(i+1, N):
  
        count = INF
        for k in range(N):   
            count = min(count, A[i][k] + A[k][j])
        
        if A[i][j] > count:
            print(-1)
            exit()

        if A[i][j] < count:
            answer += A[i][j]
        
print(answer)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
buildings = list(map(int, input().split()))

# a[1:]で大きさが上位K-1についてフラグを付ける
# フラグがついているのと前回のものの差分＋１をしていく
# この処理をK-1回行った段階で終了させる

target_list = sorted(buildings[1:], reverse=True)[:K-1]

i = 0 #ターゲットリストの添え字
cost = 0
before_building = buildings[0]

for building in buildings[1:]:

    if building == target_list[i]:
        cost += max(before_building - building + 1, 0)
        before_building += 1
        # print('cost: ', cost)
        # print('before_building: ', before_building)
        i += 1

    if i == K:
        break

print(cost)

Fixed submission:
from itertools import combinations
N, K = map(int, input().split())
A = list(map(int, input().split()))
mn = 10**18
for B in combinations(range(1,N),K-1): # 一番左は固定
    mx = A[0] # 初期値は一番左の建物
    score = 0
    for n in range(1,N):
        if n in B: # 見えるようにすべき建物なら
            if A[n] <= mx: # 低ければ高くする
                mx += 1
                score += (mx - A[n])
            else: # 高さが十分なら何もしない。最大値を更新
                mx = A[n]
        else:
            mx = max(mx, A[n]) # 見えなくても良い建物なら、最大値を更新
    mn = min(mn, score)
print (mn)
Buggy python submission (verdict: Runtime Error):
5
1 2 1 1 3

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

    for i in range(1, N):
        if A[i - 1] > A[i]:
            return "No"
        elif A[i] != A[i - 1]:
            A[i] -= 1
    return "Yes"
print(main())
Buggy python submission (verdict: Runtime Error):
S=input();print('TBD'if S[5]*4+S[6]>=4 else'Heisei')

Fixed submission:
S=input();print('TBD'if int(S[5])*5+int(S[6])>=5else'Heisei')
Buggy python submission (verdict: Runtime Error):
A,B = map(int, raw_input().split())
print((A-1)*(B-1))

Fixed submission:
A,B = map(int, input().split())
print((A-1)*(B-1))

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=[105,135,165,195,189]
for i in renge(5):
 if n>=a[i]:
  s=i+1
print(s)

Fixed submission:
A,B = map(int, input().split())
print((A-1)*(B-1))
Buggy python submission (verdict: Runtime Error):
n=input()
s=0
a=[105,135,165,195,189]
for i in a:
  if n>=i:
    s+=1
print(s)

Fixed submission:
n=int(input())
s=0
a=[105,135,165,195,189]
for i in a:
 if n>=i:
  s+=1
print(s)
Buggy python submission (verdict: Runtime Error):
a=int(input())
b=''
while a:
  s=str(a&1)+s
  n=-(n//2)
print(b if b else 0)

Fixed submission:
a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)

print(''.join(map(str,b[::-1])))

Buggy python submission (verdict: Runtime Error):
a=int(input())
b=[]
if a==0:
  print(0)
else:
  while a:
	b.append(a&1)
	a=int((a-(a&1))/(-2))
  print(''.join(map(str,b)))

Fixed submission:
a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)

print(''.join(map(str,b[::-1])))

Buggy python submission (verdict: Runtime Error):
a=int(input())
b=[]
if(a==0)print(0)
else:
  while a:
	b.append(a&1)
	a=int((a-(a&1))/(-2))
  print(''.join(map(str,b)))

Fixed submission:
a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)

print(''.join(map(str,b[::-1])))

Buggy python submission (verdict: Runtime Error):
a=int(input())
b=[]
if(a==0)print(0)
while a:
	b.append(a&1)
	a=int((a-(a&1))/(-2))
print(''.join(map(str,b)))

Fixed submission:
a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)

print(''.join(map(str,b[::-1])))
Buggy python submission (verdict: Runtime Error):
a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)
print(''.join(map(str,b[::-1])))

Fixed submission:
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
a[0]%=m
for i in range(1,n+1):
	a[i]+=a[i-1]
	a[i]%=m
a.sort()
p=0
s=0
for i in range(1,n+1):
	if a[i]-a[p]:
		l=a[i]
		p=i-p
		s+=p*(p-1)
		p=i
p=n-p
s+=p*(p+1)
print(int(s/2))

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=list(map(int,input().split()))
a[0]%=m
for i in range(1,n):
	a[i]+=a[i-1]
	a[i]%=m
a.sort()
p=0
s=0
for i in range(1,n):
	if a[i]-a[p]:
		p=i-p
		s+=p*(p-1)/2
		p=i
p=n-p
s+=p*(p+1)/2
print(s)n,m=map(int,input().split())
a=list(map(int,input().split()))
a[0]%=m
for i in range(1,n):
	a[i]+=a[i-1]
	a[i]%=m
a.sort()
l=0
p=0
s=0
for i in range(0,n):
	if a[i]-l:
		p=i-p
		s+=p*(p+1)/2
		p=i
		l=a[p]
p=n-p
s+=(p+1)*(p+2)/2
print(s/2)

Fixed submission:
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
a[0]%=m
for i in range(1,n+1):
	a[i]+=a[i-1]
	a[i]%=m
a.sort()
p=0
s=0
for i in range(1,n+1):
	if a[i]-a[p]:
		l=a[i]
		p=i-p
		s+=p*(p-1)
		p=i
p=n-p
s+=p*(p+1)
print(int(s/2))
Buggy python submission (verdict: Runtime Error):
K=int(input())
A,B=map(int,input())
if (A-1)/K == B/K:
  print('NG')
else:
  print('OK')

Fixed submission:
K=int(input())
A,B=map(int,input().split())
if (A-1)//K == B//K:
  print('NG')
else:
  print('OK')
Buggy python submission (verdict: Runtime Error):
S,W=map(int,intput().split())
if S<=W:
  print("unsafe")
else:
  print("safe")

Fixed submission:
S,W=map(int,input().split())
if S<=W:
  print("unsafe")
else:
  print("safe")
Buggy python submission (verdict: Runtime Error):
A,B=map(int,input().split())
if B < A:
  A,B=B,A
for i in range B;
 print(A, end="")
print()

Fixed submission:
A,B=map(int,input().split())
if B < A:
  A,B=B,A
for i in range(B):
 print(A, end="")
print()
Buggy python submission (verdict: Runtime Error):
A=int(input())
B=int(input())
for i in raneg(3):
  if i+1 !=A && i+1 != B:
    print(i+1)

Fixed submission:
A=int(input())
B=int(input())
for i in range(3):
  if i+1 !=A and i+1 != B:
    print(i+1)
Buggy python submission (verdict: Runtime Error):
A,B=maps(int,input().split())
print(max(max(A+B,A-B),A*B))

Fixed submission:
A,B=map(int,input().split())
print(max([A+B,A-B,A*B]))

Buggy python submission (verdict: Runtime Error):
A,B=maps(int,input().split())
print(max([A+B,A-B,A*B]))

Fixed submission:
A,B=map(int,input().split())
print(max([A+B,A-B,A*B]))
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
if (N+M)%2==0:
  print((N+M)/2)
 else:
  print("IMPOSSIBLE")

Fixed submission:
N,M=map(int,input().split())
if (N+M)%2==0:
  print((N+M)//2)
else:
  print("IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
N = int(input())
if N < 1200:
  print("ABC")
elif N < 2800:
  print("ARC")
else
  print("AGC")



Fixed submission:
N = int(input())
if N < 1200:
  print("ABC")
elif N < 2800:
  print("ARC")
else:
  print("AGC")