Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):

n,a,b = map(int, input().split())
MOD = 10**9 + 7
allpair = pow(2,n,MOD)

def combo(n,k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= MOD

    d = 1
    for i in range(1, k+1):
        d *= i
        d %= MOD

    return (c * pow(d, mod-2, MOD)) % MOD

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)


Fixed submission:
n,a,b = map(int, input().split())
MOD = 10**9 + 7
allpair = pow(2,n,MOD)

def combo(n,k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= MOD

    d = 1
    for i in range(1, k+1):
        d *= i
        d %= MOD

    return (c * pow(d, MOD-2, MOD)) % MOD

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):

n,a,b = map(int, input().split())
MOD = 10**9 + 7
allpair = pow(2,n,MOD)

def combo(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    
    return result

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)


Fixed submission:
n,a,b = map(int, input().split())
MOD = 10**9 + 7
allpair = pow(2,n,MOD)

def combo(n,k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= MOD

    d = 1
    for i in range(1, k+1):
        d *= i
        d %= MOD

    return (c * pow(d, MOD-2, MOD)) % MOD

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)

Buggy python submission (verdict: Runtime Error):

n,a,b = map(int, input().split())
MOD = 10**9 + 7
allpair = pow(2,n,MOD)

N = n
# 早いnCrの準備ここから
fact = [0] * (N+1)
fact_inv = [0] * (N+1)
inv = [0] * (N+1)

fact[0] = fact[1]  = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2, N+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD//i) % MOD # //で良いのかな?
    fact_inv[i] = fact_inv[i-1] * inv[i] % MOD

def combo(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fact[n] * (fact_inv[k] * fact_inv[n-k] % MOD) % MOD

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)


Fixed submission:
n,a,b = map(int, input().split())
MOD = 10**9 + 7
allpair = pow(2,n,MOD)

def combo(n,k):
    c = 1
    for i in range(k):
        c *= n - i
        c %= MOD

    d = 1
    for i in range(1, k+1):
        d *= i
        d %= MOD

    return (c * pow(d, MOD-2, MOD)) % MOD

print((allpair - combo(n, a) - combo(n, b) - 1) % MOD)
Buggy python submission (verdict: Runtime Error):
S,T = input().split()
N,M = list(map(int, input().split()))
s = input()
print(f"{N-1} {M}" if s == S else f"{N} {M-1}") 

Fixed submission:
S,T = input().split()
N,M = list(map(int, input().split()))
s = input()
if s == S:
  print(N-1, M)
else:
  print(N, M-1)
Buggy python submission (verdict: Time Limit Exceeded):

H, N = map(int, input().split())
ab_list = [list(map(int, input().split())) for _ in range(N)]

max_a = max(a for a,b in ab_list)
W = H + 1 + max_a
dp = [0] * W

for i in range(W):
    dp[i] = 10**9
    for a,b in ab_list:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H-1:]))

Fixed submission:

H, N = map(int, input().split())
ab_list = [list(map(int, input().split())) for _ in range(N)]

max_a = max(a for a,b in ab_list)
W = H + 1 + max_a
dp = [0] * W

for i in range(W):
    dp[i] = min(dp[i-a]+b for a,b in ab_list)

print(min(dp[H-1:]))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A_list = list(map(int, input().split()))
MOD = 10**9 + 7

zeros = [0] * 61
ones = [0] * 61

for a in A_list:
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            ones[i] += 1
        else:
            zeros[i] += 1

res = 0
for a in A_list:
    twice = 1
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            cnt = zeros[i]
            ones[i] -= 1
        else:
            cnt = ones[i]
            zeros[i] -= 1
        res += twice * cnt
        twice *= 2
    res %= MOD
print(res)

Fixed submission:
N = int(input())
A_list = list(map(int, input().split()))
MOD = 10**9 + 7

zeros = [0] * 61
ones = [0] * 61

for a in A_list:
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            ones[i] += 1
        else:
            zeros[i] += 1

res = 0
for a in A_list:
    twice = 1
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            cnt = zeros[i]
            ones[i] -= 1
        else:
            cnt = ones[i]
            zeros[i] -= 1
        res += twice * cnt
        twice *= 2
    res %= MOD
print(res)

Buggy python submission (verdict: Runtime Error):
%%time
from functools import reduce
from operator import xor

A_arr = list(map(int, input().split()))

res = 0
for i,Ai in enumerate(A_arr[:-1]):
    res += sum(map(lambda yj: Ai ^ yj, A_arr[i+1:]))
print(res%(10**9 + 7))

Fixed submission:
N = int(input())
A_list = list(map(int, input().split()))
MOD = 10**9 + 7

zeros = [0] * 61
ones = [0] * 61

for a in A_list:
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            ones[i] += 1
        else:
            zeros[i] += 1

res = 0
for a in A_list:
    twice = 1
    for i, b in enumerate([1 if (a >> j & 1) else 0 for j in range(61)]):
        if b == 1:
            cnt = zeros[i]
            ones[i] -= 1
        else:
            cnt = ones[i]
            zeros[i] -= 1
        res += twice * cnt
        twice *= 2
    res %= MOD
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import math
X,Y = list(map(int, input().split()))
cnts = [0,0]
while X>0 and Y>0:
    if X <= Y:
        cnts[1] += 1
        X -= 1
        Y -= 2
    else:
        cnts[0] += 1
        X -= 2
        Y -= 1
        
if X == 0 and Y == 0:
    i = cnts[0]
    j = cnts[1]
    print(math.factorial(i+j)//(math.factorial(i)*math.factorial(j)) % (10**9 + 7))
else:
    print(0)

Fixed submission:

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

X,Y = list(map(int, input().split()))

# X = 2n+m, Y = n+2mとして
n = (2*X-Y)//3
m = (Y-n)//2

mod = 10**9+7 #出力の制限
N = n+m
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


if (X + Y) % 3 != 0:
    print(0)
elif n < 0 or m < 0:
    print(0)
else:
    print(cmb(n+m, n, mod))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
Ls = list(map(int, input().split()))

Ls = sorted(Ls)
cnt = 0
for i in range(N):
    l1 = Ls[i]
    for j in range(i+1, N):
        l2 = Ls[j]
        cnt += len([l for l in Ls[j+1:] if l <(l1+l2)])
print(cnt)

Fixed submission:
import bisect
N = int(input())
Ls = list(map(int, input().split()))
 
Ls = sorted(Ls)
cnt = 0
for i in range(N):
    l1 = Ls[i]
    for j in range(i+1, N):
        l2 = Ls[j]
        ind = bisect.bisect_left(Ls, l1 + l2)
        cnt += ind - j - 1
print(cnt)
Buggy python submission (verdict: Runtime Error):

def func():
    if len(S) == 1:
        return int(K/2)
    
    cnt = 1
    pre_s = S[0]
    tup_list = []
    for s in S[1:]:
        if pre_s == s:
            cnt += 1
        else:
            tup_list.append([pre_s, cnt])
            cnt = 1
        pre_s = s
    else:
        tup_list.append([pre_s, cnt])

    if len(tup_list) == 1:
        return int(cnt* K/2)
    
    if tup_list[0][0] == tup_list[-1][0]:
        pre_tup = tup_list.pop()[1]
        tup_list[0][1] += pre_tup
    res = -1 if pre_tup % 2 == 1 else 0
    for _,cnt in tup_list:
        res += int(cnt/2) * K
    return max(0,res) 

S = input()
K = int(input())
print(func())

Fixed submission:

def func():
    if len(S) == 1:
        return int(K/2)
    
    cnt = 1
    pre_s = S[0]
    tup_list = []
    for s in S[1:]:
        if pre_s == s:
            cnt += 1
        else:
            tup_list.append([pre_s, cnt])
            cnt = 1
        pre_s = s
    else:
        tup_list.append([pre_s, cnt])

    if len(tup_list) == 1:
        return int(cnt* K/2)
    
    ext = 0
    if tup_list[0][0] == tup_list[-1][0]:
        a = tup_list.pop()[1]
        b = tup_list[0][1]
        ext = int(a/2) + int(b/2) - int((a+b)/2)
        tup_list[0][1] += a
        
    res = 0
    for _,cnt in tup_list:
        res += int(cnt/2) * K
    return res + ext
    
S = input()
K = int(input())
print(func())
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
As = list(map(int, input().split(" ")))

s = ""
for i in range(1,N+1):
    for j in range(N):
        if As[j] == i:
            s += str(j+1)+" "
print(s)

Fixed submission:
N = int(input())
As = list(map(int, input().split(" ")))
arr = [[] for i in range(N)]

for i,A in enumerate(As):
    arr[A-1] = i+1
print(" ".join(list(map(str, arr))))
Buggy python submission (verdict: Time Limit Exceeded):
def prime_pair(n):
    pairs = {}
    tmp = n
    for i in range(2, n):
        if tmp % i != 0:
            continue
        ex = 0
        while tmp % i == 0:
            ex += 1
            tmp /= i
        pairs[i] = ex
    return pairs

def gcd(a,b):
    if b % a == 0:
        return a
    return gcd(b % a, a)


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

ppa = prime_pair(A)
ppb = prime_pair(B)

g = gcd(A,B)
ppg = prime_pair(g)

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

Fixed submission:
def factorization(n):
    arr = [[1,1]]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
A,B =list(map(int, input().split(" ")))

val = min(A,B)
lim = int(val ** 0.5)


ms = factorization(min(A,B)) 
res = []
maxi = max(A,B)

for v, _ in ms:
    if maxi % v == 0:
        res.append(v)
print(len(res))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N,K,Q = list(map(int, input().split()))
As = [int(input()) for _ in range(Q)]

res = np.zeros(N) + K
for a in As:
    res -= 1
    res[a-1] += 1

for i in range(N):
    if res[i] > 0 :
        print('Yes')
    else:
        print('No')

Fixed submission:
import numpy as np

N,K,Q = list(map(int, input().split()))
As = [int(input()) for _ in range(Q)]

res = np.zeros(N)
for a in As:
    res[a-1] += 1
    
for i in range(N):
    if res[i] > (Q - K) :
        print('Yes')
    else:
        print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()

maxs = 0
for i, s1 in enumerate(S):
    if i + maxs > len(S):
        break
    matchs = S[i:i+maxs+1]
    for j in range(i+maxs+1, len(S)-maxs):
        # 以下でmatchしてたらここに戻りたい
        for k in range(j,len(S)-maxs):
            if i + maxs >= j:
                break
            checks = S[j:j+maxs+1]
            if matchs == checks:
                maxs = len(matchs)
                matchs = S[i:i+maxs+1]
print(maxs)

Fixed submission:
N = int(input())
S = input()

i = j = 0
ans = 0
while j < N-1:
    if S[i:j] in S[j:]:
        ans = max(ans, j-i)
        j += 1
    else:
        i += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
Hs = list(map(int, input().split()))
max_cnt = 0
tmp = 1 if Hs[0] >= Hs[1] else 0
for i in range(1,N):
    if Hs[i-1] < Hs[i]:
        max_cnt = max(max_cnt, tmp)
        tmp = 0
    else:
        tmp += 1
print(max(max_cnt, tmp))

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

max_cnt = 0
cnt = 0
for i in range(N-1):
    if Hs[i] < Hs[i+1]:
        max_cnt = max(max_cnt, cnt)
        cnt = 0
    else:
        cnt += 1
print(max(max_cnt, cnt))
Buggy python submission (verdict: Time Limit Exceeded):
n,m = input().split(" ")
n = int(n)
m = int(m)

arr = [[] for _ in range(m)]

for i in range(n):
  a,b = input().split(" ")
  a = int(a)
  b = int(b)
  
  if a > m:
    continue
    
  arr[a-1].append(b)

vs = []
res = 0
for item in arr:
  vs.extend(item)
  if len(vs) == 0:
    continue
    
  vs.sort()
  maxi = vs.pop(-1)
  res += maxi
  
print(res)

Fixed submission:
import heapq
n,m = input().split(" ")
n = int(n)
m = int(m)

arr = [[] for _ in range(m)]

for i in range(n):
  a,b = input().split(" ")
  a = int(a)
  b = - int(b) # for heap
  
  if a > m:
    continue
    
  arr[a-1].append(b)

vs = []
heapq.heapify(vs)

res = 0
for item in arr:
  for v in item:
	  heapq.heappush(vs, v)
  
  if len(vs) == 0:
    continue
    
  maxi = heapq.heappop(vs)
  res += (-1* maxi)
  
print(res)

Buggy python submission (verdict: Runtime Error):
n,m = input().split(" ")
n = int(n)
m = int(m)

arr = [[] for _ in range(m)]

for i in range(n):
  a,b = input().split(" ")
  a = int(a) -1
  b = int(b)
  
  if a > m:
    continue
  arr[a].append(b)

vs = []
res = 0
for item in arr:
  vs[len(vs):len(vs)] = item
  if len(vs) == 0:
    continue
    
  vs.sort()
  maxi = vs.pop(-1)
  res += maxi
  
print(res)

Fixed submission:
import heapq
n,m = input().split(" ")
n = int(n)
m = int(m)

arr = [[] for _ in range(m)]

for i in range(n):
  a,b = input().split(" ")
  a = int(a)
  b = - int(b) # for heap
  
  if a > m:
    continue
    
  arr[a-1].append(b)

vs = []
heapq.heapify(vs)

res = 0
for item in arr:
  for v in item:
	  heapq.heappush(vs, v)
  
  if len(vs) == 0:
    continue
    
  maxi = heapq.heappop(vs)
  res += (-1* maxi)
  
print(res)
Buggy python submission (verdict: Time Limit Exceeded):

import bisect

def main():
    N = int(input())
    l = []

    for i in range(N):
        a = int(input())
        if len(l) == 0 or a <= l[0]:
            l.insert(0,a)
        else:
            ind = bisect.bisect_left(l, a)
            l[ind-1] = a

    print(len(l))

if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque
import bisect

def main():
    N = int(input())
    l = deque([])

    for i in range(N):
        a = int(input())
        if len(l) == 0 or a <= l[0]:
            l.appendleft(a)
        else:
            ind = bisect.bisect_left(l, a)
            l[ind-1] = a

    print(len(l))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):

import bisect

def main():
    N = int(input())
    l = []

    for i in range(N):
        a = int(input())
        if len(l) == 0 or a <= l[0]:
            l.insert(0,a)
        else:
            ind = bisect.bisect_left(l, a)
            l[ind-1] = a

    print(len(l))

if __name__ == "__main__":
    main()


Fixed submission:
from collections import deque
import bisect

def main():
    N = int(input())
    l = deque([])

    for i in range(N):
        a = int(input())
        if len(l) == 0 or a <= l[0]:
            l.appendleft(a)
        else:
            ind = bisect.bisect_left(l, a)
            l[ind-1] = a

    print(len(l))

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())
a_list = [int(input()) for _ in range(M)]

MOD = 10**9+7

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

res = 1
bef = -1
for a in a_list:
    res *= dp[a-bef]
    res %= MOD
    bef = a

res *= dp[N-bef+1]
res %= MOD

print(res)

    

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

MOD = 10**9+7

dp = [0] * (10**5 + 3)
dp[1] = 0
dp[2] = 1
dp[3] = 2
for i in range(3, len(dp)):
    dp[i] = dp[i-1] + dp[i-2] 

res = 1
bef = -1
if M > 0:
    for a in a_list:
        res *= dp[a-bef]
        res %= MOD
        bef = a
res *= dp[N-bef+1]
res %= MOD

print(res)
Buggy python submission (verdict: Time Limit Exceeded):
N,M = list(map(int, input().split(" ")))
Xs = sorted(list(map(int, input().split(" "))))

if N >= M :
	print(0)
	exit()
	
darr = [Xs[i+1] - Xs[i]for i in range(M-1)]


# ??
for i in range(N-1):
	darr.pop(darr.index(max(darr)))
	
print(sum(darr))

Fixed submission:
import heapq
N,M = list(map(int, input().split(" ")))
Xs = sorted(list(map(int, input().split(" "))))

if N >= M :
	print(0)
	exit()
	
darr = [Xs[i+1] - Xs[i]for i in range(M-1)]

# print(darr)
heapq.heapify(darr)
res = 0

for _ in range(M - N):
	res += heapq.heappop(darr)
	
print(res)
Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())

for i in range(int(M**0.5), 1, -1):
    if M % i != 0:
        continue
    if M//i >= N:
        break

print(i)


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

maxi = 1
for i in range(int(M**0.5), 0, -1):
    if M % i != 0:
        continue
    if M//i >= N:
        maxi = max(maxi, i)
    if i >= N:
        maxi = max(maxi, M//i)

print(maxi)
Buggy python submission (verdict: Runtime Error):

near = abs(xlist[lpos]) if (abs(xlist[lpos]) < abs(xlist[rpos])) else abs(xlist[rpos])
bet = abs(xlist[lpos] - xlist[rpos])

ans = bet + near

for i in range(N-K):
    lpos += 1
    rpos += 1

    near = abs(xlist[lpos]) if (abs(xlist[lpos]) < abs(xlist[rpos])) else abs(xlist[rpos])
    bet = abs(xlist[lpos] - xlist[rpos])

    tmp = bet+near

    if tmp < ans:
        ans = tmp


print(ans)


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

lpos = 0
rpos = K-1

near = abs(xlist[lpos]) if (abs(xlist[lpos]) < abs(xlist[rpos])) else abs(xlist[rpos])
bet = abs(xlist[lpos] - xlist[rpos])

ans = bet + near

for i in range(N-K):
    lpos += 1
    rpos += 1

    near = abs(xlist[lpos]) if (abs(xlist[lpos]) < abs(xlist[rpos])) else abs(xlist[rpos])
    bet = abs(xlist[lpos] - xlist[rpos])

    tmp = bet+near

    if tmp < ans:
        ans = tmp


print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())

ones = 0
for st in S:
    if st != '1':
        break
    else:
        ones += 1

if K < ones:
    print('1')
else:
    print(S[ones])

Fixed submission:
S = input()
K = int(input())

ones = 0
for st in S:
    if st != '1':
        break
    else:
        ones += 1

if K-1 < ones:
    print('1')
else:
    print(S[ones])

Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())

ones = 0
for st in S:
    if st != '1':
        break
    else:
        ones += 1

if K < ones:
    print('1')
else:
    print(S[ones])

Fixed submission:
S = input()
K = int(input())

ones = 0
for st in S:
    if st != '1':
        break
    else:
        ones += 1

if K-1 < ones:
    print('1')
else:
    print(S[ones])
Buggy python submission (verdict: Runtime Error):
nm = input()
n, m = nm.split()
n = int(n)
m = int(m)

arr = [[] for i in range(n)]

for i in range(m):
	ab = input()
	a, b = ab.split()
	a = int(a)
	b = int(b)
	arr[a-1].append(b)	

cnt = 0	
sting = 0
for i,isl in enumerate(arr):
	sting = isl[0]
	for j in arr[i:sting]:
		if (i == sting):
			cnt += 1
print(cnt)

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

arr = [[] for i in range(n)]

for i in range(m):
	a, b = list(map(int, input().split()))
	arr[a-1].append(b)	

cnt = 0	
sting = n+1
for i,isl in enumerate(arr):
	isl.sort()
	if sting == i+1:
		cnt += 1
		sting = n+1

	if len(isl) == 0:
		continue
		
	if isl[0] < sting:
		sting = isl[0]
print(cnt)

Buggy python submission (verdict: Runtime Error):
nm = input()
n, m = nm.split()
n = int(n)
m = int(m)

arr = [[] for i in range(n)]

for i in range(m):
	ab = input()
	a, b = ab.split()
	a = int(a)
	b = int(b)
	arr[a-1].append(b)	

cnt = 0	
sting = 0
for i,isl in enumerate(arr):
	sting = isl[0]
	for j in arr[i:sting]:
		if (i == sting):
			cnt += 1
print(cnt)

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

arr = [[] for i in range(n)]

for i in range(m):
	a, b = list(map(int, input().split()))
	arr[a-1].append(b)	

cnt = 0	
sting = n+1
for i,isl in enumerate(arr):
	isl.sort()
	if sting == i+1:
		cnt += 1
		sting = n+1

	if len(isl) == 0:
		continue
		
	if isl[0] < sting:
		sting = isl[0]
print(cnt)

Buggy python submission (verdict: Runtime Error):
nm = input()
n, m = nm.split()
n = int(n)
m = int(m)

arr = [[] for i in range(n)]

for i in range(m):
	ab = input()
	a, b = ab.split()
	a = int(a)
	b = int(b)
	arr[a-1].append(b)	

cnt = 0	
sting = 0
for i,isl in enumelate(arr):
	sting = isl[0]
	for j in arr[i:sting]:
		if (i == sting):
			cnt += 1
print(cnt)

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

arr = [[] for i in range(n)]

for i in range(m):
	a, b = list(map(int, input().split()))
	arr[a-1].append(b)	

cnt = 0	
sting = n+1
for i,isl in enumerate(arr):
	isl.sort()
	if sting == i+1:
		cnt += 1
		sting = n+1

	if len(isl) == 0:
		continue
		
	if isl[0] < sting:
		sting = isl[0]
print(cnt)
Buggy python submission (verdict: Runtime Error):
N = int(input())
dic = {}
for c in "MARCH":
    dic[c] = 0
myset = set(list("MARCH"))
for _ in range(N):
    c = input()[0]
    if c in myset:
        dic[c] += 1

res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            res += dic["MARCH"[i]] * dic["MARCH"[j]] * dic["MARCH"[k]]
print(res)

Fixed submission:
N = int(input())
dic = {}
for c in "MARCH":
    dic[c] = 0
myset = set(list("MARCH"))
for _ in range(N):
    c = input()[0]
    if c in myset:
        dic[c] += 1

res = 0
for i in range(5-2):
    for j in range(i+1, 5-1):
        for k in range(j+1, 5):
            res += dic["MARCH"[i]] * dic["MARCH"[j]] * dic["MARCH"[k]]
print(res)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A_list = list(map(int, input().split())
 
a_sum = 0
b_sum = 0
for i in range(N//2):
  a,b = (A_list[2*i], A_list[2*i + 1]) if A_list[2*i] > A_list[2*i + 1] else (A_list[2*i + 1], A_list[2*i])
  a_sum += a
  b_sum += b
 
print(a_sum - b_sum)
 

Fixed submission:
N = int(input())
A_list = sorted(list(map(int, input().split())))[::-1]
a_sum = 0
b_sum = 0

for i in range(N):
    if i % 2 == 0:
        a_sum += A_list[i]
    else:
        b_sum += A_list[i]
print(a_sum - b_sum)

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

a_sum = 0
b_sum = 0
for i in range(N//2):
  a,b = (A_list[2*i], A_list[2*i + 1]) if A_list[2*i] > A_list[2*i + 1] else (A_list[2*i + 1], A_list[2*i])
  a_sum += a
  b_sum += b

print(a_sum - b_sum)
 

Fixed submission:
N = int(input())
A_list = sorted(list(map(int, input().split())))[::-1]
a_sum = 0
b_sum = 0

for i in range(N):
    if i % 2 == 0:
        a_sum += A_list[i]
    else:
        b_sum += A_list[i]
print(a_sum - b_sum)