Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

F_str = input().split()
F = [int(f) for f in F_str]
N = F[0]
M = F[1]

WA_dict = {}
AC_list = []

for i in range(M):
    S_str = input().split()
    S = [str(s) for s in S_str]
    if(S[1] == "AC"):
        AC_list.append(S[0])
    elif(S[0] not in AC_list):
        WA_dict.setdefault(S[0], 0)
        WA_dict[S[0]] += 1

AC_set = list(set(AC_list))

WA_count = 0

for item in AC_set:
    if(item in WA_dict):
        WA_count += WA_dict[item]

print(str(len(AC_set)) + " " + str(WA_count))

### FIXED CODE ###

F_str = input().split()
F = [int(f) for f in F_str]
N = F[0]
M = F[1]

WA_list = [0 for _ in range(N)]
AC_list = [0 for _ in range(N)]

for i in range(M):
    S_str = input().split()
    S = [str(s) for s in S_str]
    if(S[1] == "AC"):
        AC_list[int(S[0])-1] = 1
    elif(AC_list[int(S[0])-1] != 1):
        WA_list[int(S[0])-1] += 1

WA_count = 0
AC_count = 0

for i in range(N):
    if(AC_list[i] == 1):
        AC_count += 1
        WA_count += WA_list[i]

print(AC_count, WA_count)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
count = 0
while A:
  a = A[0]
  b = A.count(a)
  if b%2 == 1:
    count += 1
  del A[:b]
print(count)


### FIXED CODE ###

import collections
N = int(input())
A = [int(input()) for i in range(N)]
C = list(collections.Counter(A).values())
counter = 0
for x in C:
  if x%2 == 1:
    counter += 1
print(counter)
### BUGGY CODE ###

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


for _ in range(M):
    l, r = list(map(int, input().split()))
    X[l-1][r-1] += 1
C = []
for line in X:
    tmp = [0, ]
    for c in line:
        tmp.append(tmp[-1] + c)
    C.append(tmp)
query = [map(int, input().split()) for _ in range(Q)]
# print(X)
# print(C)

for p, q in query:
    ans = 0
    for i, line in enumerate(C):
        if p-1 <= i and i <= q-1:
            ans += line[q] - line[p-1]
    print(ans)


### FIXED CODE ###

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


for _ in range(M):
    l, r = list(map(int, input().split()))
    X[l-1][r-1] += 1
C = []
for line in X:
    tmp = [0, ]
    for c in line:
        tmp.append(tmp[-1] + c)
    C.append(tmp)
query = [map(int, input().split()) for _ in range(Q)]
# print(X)
# print(C)

for p, q in query:
    ans = 0
    for i, line in enumerate(C):
        if p-1 <= i and i <= q-1:
            ans += line[q] - line[p-1]
    print(ans)
### BUGGY CODE ###

def main():
    S = input()
    Q = int(input())
    ans = S
    rev = False # rev=1で反転した状態
    for i in range(Q):
        query = input()
        if len(query)==1:
            rev = not rev
        else:
            tmp = list(query.split())
            f = int(tmp[1])
            c = tmp[2]
            if rev:
                ans = ans+c if f==1 else c+ans
            else:
                ans = c+ans if f==1 else ans+c

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

main()


### FIXED CODE ###

def main():
    S = input()
    Q = int(input())
    rev = False # rev=1で反転した状態
    tail = ""
    head = ""
    for i in range(Q):
        query = input()
        if len(query)==1:
            rev = not rev
        else:
            tmp = list(query.split())
            f = int(tmp[1])
            c = tmp[2]
            if rev:
                if f==1:
                    tail+=c
                else:
                    head=c+head
            else:
                if f==1:
                    head=c+head
                else:
                    tail+=c

    ans = tail[::-1]+S[::-1]+head[::-1] if rev else head+S+tail
    print(ans)

main()
### BUGGY CODE ###

N, Q = map(int, input().split())
S = [i if i in 'AC' else '-' for i in input()]
for i in range(Q):
  l, r = map(int, input().split())
  a = ''.join([S[i] if S[i] == 'A' and S[i+1] == 'C' else '-' for i in range(l-1, r-1)])
  a = [i for i in a.split('-') if len(i) > 0]
  print(len(a))



### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
S = [1 if i > 0 and S[i-1] == 'A' and S[i] == 'C' else 0 for i in range(N)]
T = [0 for _ in range(N)]
for i in range(N):
    T[i] = S[i]
    if i > 0:
        T[i] += T[i-1]
for i in range(Q):
  l, r = map(int, input().split())
  print(T[r-1]-T[l-1])
### BUGGY CODE ###

n,k,*a,=map(int,open(0).read().split())
def f(li):
	b=[0]*(n+1)
	for i,x in enumerate(li):
		b[max(0,i-x)]+=1
		b[min(i+x+1,n)]-=1
	for i in range(n):
		b[i+1]+=b[i]
	return b[:-1]
for _ in range(k):
	a=f(a)
	if a==[n]*n:
		print(*a)
		exit()
print(*a)

### FIXED CODE ###

n,k,*a,=map(int,open(0).read().split())
def f(li):
	b=[0]*(n+1)
	for i,x in enumerate(li):
		b[max(0,i-x)]+=1
		b[min(i+x+1,n)]-=1
	for i in range(n):
		b[i+1]+=b[i]
	return b[:-1]
for _ in range(k):
	a=f(a)
	if a==[n]*n:
		print(*a)
		exit()
print(*a)
### BUGGY CODE ###

from copy import copy
from collections import Counter
from scipy.special import comb

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

for k in range(n):
  a = copy(A)
  a.pop(k)
  c = Counter(a)
  ans = 0
  for i in range(1,n+1):
    ans += comb(c[i],2,exact=True)
  print(ans)

### FIXED CODE ###

from copy import copy
from collections import Counter
from scipy.special import comb

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

C = Counter(A)
S = 0
for i in range(1,n+1):
  S += comb(C[i],2,exact=True)

for k in range(n):
  p = A[k]
  ans = S - comb(C[p],2,exact=True) + comb(C[p]-1,2,exact=True)
  print(ans)
### BUGGY CODE ###

from collections import defaultdict
import heapq
N,M=map(int,input().split())
x=defaultdict(list)
for i in range(N):
    a,b=map(int,input().split())
    x[a].append(-b)
y=[]
an=0
for i in range(M+1):
    y+=x[i]
    heapq.heapify(y)
    try:
        an-=heapq.heappop(y)
    except:
        pass
print(an)

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
x={}
for i in range(M+1):
    x[i]=[]
for i in range(N):
    a,b=map(int,input().split())
    if a>M:
        continue
    x[a].append(-b)
y=[]
an=0
for i in range(M+1):
    for n in x[i]:
        heapq.heappush(y,n)
    try:
        an-=heapq.heappop(y)
    except:
        pass
print(an)
### BUGGY CODE ###

N=int(input())

seq=[]

for i in range(N):

    a= int(input())
    
    seq.append(a)

left=[0]
for i in range(N-1):
    left_i=max(left[i],seq[i])

    left.append(left_i)

right=[0]

for j in range(N-1):
    right_j = max(right[j],list(reversed(seq))[j])

    right.append(right_j)

right = list(reversed(right))

for k in range(N):
    print(max(left[k],right[k]))

### FIXED CODE ###

N=int(input())

seq=[]

for i in range(N):
    a= int(input())
    seq.append(a)

import heapq

tmp=list(map(lambda x: x*(-1),seq))
heapq.heapify(tmp)

a=heapq.heappop(tmp)*(-1)
b=heapq.heappop(tmp)*(-1)

for j in range(N):
    if seq[j]==a:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

from collections import deque
from collections import defaultdict

N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}
test={}

for i in range(M):
	L,R,D=map(int,raw_input().split())
	if i==0:start=L
	nl[L].append(R)
	nl[R].append(L)
	cost[(L,R)]=D
	cost[(R,L)]=-D
	test[(L,R)]=D


d=defaultdict(lambda: -1)

def dfs(start):
	V=[ 0 for i in range(N+1) ]
	q = deque([]) 
	V[start]=1
	d[start]=0
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i]!=1:
				V[i]=1
				q.append(i)
				d[i]=d[v]+cost[(v,i)]


for i,j in test.items():
	x1=i[0]
	x2=i[1]

	if d[x1]==-1:
		dfs(x1)
	if d[x2]-d[x1]==j:
		continue
	else:
		print "No"
		quit()
else:
	print "Yes"




### FIXED CODE ###

from collections import deque
from collections import defaultdict

N,M=map(int,raw_input().split())
nl=[ [] for i in range(N+1) ]
cost={}

for i in range(M):
	L,R,D=map(int,raw_input().split())
	if i==0:start=L
	nl[L].append(R)
	nl[R].append(L)
	cost[(L,R)]=D
	cost[(R,L)]=-D


d=[ None for i in range(N+1) ]
V=[ 0 for i in range(N+1) ]

def dfs(start):
	q = deque([]) 
	V[start]=1
	d[start]=0
	q.append(start)

	while len(q)!=0:
		v=q.pop()
		for i in nl[v]:
			if V[i]!=1:
				V[i]=1
				q.append(i)
				d[i]=d[v]+cost[(v,i)]
			else:
				if d[i]-d[v]!=cost[(v,i)]:
					print "No"
					quit()

for i in range(1,N+1):
	if V[i]==0:
		dfs(i)
else:
	print "Yes"
### BUGGY CODE ###

n= int(input())


l=[]

for i in range(n):
    l.append(input())
    l.sort()

ac=l.count('AC')
tle=l.count('TLE')
wa=l.count('WA')
re=l.count('RE')
print('AC x '+ str(ac))
print('WA x '+ str(wa))
print('TLE x '+ str(tle))
print('RE x '+ str(re))








### FIXED CODE ###

n= int(input())

ac=0
wa=0
tle=0
re=0

l=[]

for i in range(n):
    t=input()
    if(t=='AC'):
        ac=ac+1
    elif(t=='WA'):
        wa=wa+1
    elif(t=='TLE'):
        tle=tle+1
    elif(t=='RE'):
        re=re+1
  
print('AC x '+ str(ac))
print('WA x '+ str(wa))
print('TLE x '+ str(tle))
print('RE x '+ str(re))
### BUGGY CODE ###

from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
MOD = 10**9+7
def prime_table(n):
  if n < 2:
    return []
  prime = [2]
  limit = int(n**0.5)
  data = [i+1 for i in range(2,n,2)]
  while True:
    p = data[0]
    if limit <= p:
      return prime + data
    prime.append(p)
    data = [e for e in data if e%p != 0]
def modinv(a,m=MOD):
  b,u,v = m,1,0
  while b:
    t = a//b
    a,u = a-t*b,u-t*v
    a,b,u,v = b,a,v,u
  u %= m
  if u < 0:
    u += m
  return u
data = prime_table(max(a))
prime = [0] * len(data)
for i in a:
  for j in range(len(data)):
    c = 0
    while True:
      if i % data[j] == 0:
        i = i // data[j]
        c += 1
      else:
        break
    prime[j] = max(prime[j],c)
lcm = 1
for i,j in zip(data,prime):
  lcm = (lcm*pow(i,j,MOD))%MOD
c = 0
for i in a:
  c += lcm*modinv(i,MOD)
  c %= MOD
print(c)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
MOD = 10**9+7
def prime_table(n):
  if n <= 1:
    return [],[],[]
  prime = [2]
  limit = int(n**0.5)
  data = [i+1 for i in range(2,n,2)]
  isprime = [0]*(n+1)
  isprime[2] = 1
  min_factor = [0 if i%2 != 0 else 2 for i in range(n+1)]
  while True:
    p = data[0]
    prime.append(p)
    isprime[p] = 1
    pdata,data = data,[]
    for e in pdata:
      if e%p != 0:
        data.append(e)
      else:
        min_factor[e] = p
    if limit <= p:
      for i in data:
        isprime[i] = 1
        min_factor[i] = i
      return prime + data,isprime,min_factor
def modinv(a,m=MOD):
  b,u,v = m,1,0
  while b:
    t = a//b
    a,u = a-t*b,u-t*v
    a,b,u,v = b,a,v,u
  u %= m
  if u < 0:
    u += m
  return u
ma = max(a)
data,isprime,min_factor = prime_table(ma)
prime = [0] * (ma+1)
for i in a:
  if i == 1:
    continue
  d = defaultdict(int)
  while isprime[i] == 0:
    d[min_factor[i]] += 1
    i = i // min_factor[i]
  d[i] += 1
  for j,k in d.items():
    prime[j] = max(prime[j],k)
lcm = 1
for i in range(ma+1):
  if prime[i] != 0:
    lcm = (lcm*pow(i,prime[i],MOD))%MOD
c = 0
for i in a:
  c += lcm*modinv(i,MOD)
  c %= MOD
print(c)
### BUGGY CODE ###

n = int(input())
s = list(map(int, input().split())) # in演算子を使うためにはsはlistである必要がある。
q = int(input())
t = map(int, input().split())

cnt = 0

for i in t:
    if i in s:
        cnt += 1

print(cnt)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 30 11:33:59 2018
ALDS1-4a_r  バイナリサーチ

@author: maezawa
"""

def binary_search(a, key):
    n = len(a)
    left = 0
    right = n
    while left < right:
        #print(left, right)
        mid = (right+left)//2
        if a[mid] == key:
            return mid
        elif a[mid] > key:
            right = mid
        else:
            left = mid + 1
    return n

n = int(input())
s = list(map(int, input().split())) # in演算子を使うためにはsはlistである必要がある。
q = int(input())
t = map(int, input().split())

cnt = 0
for i in t:
    if binary_search(s, i) < n:
        cnt += 1

print(cnt)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * (2 ** (leng - j - 1))
            else:
                ans += bit_acc[j] * (2 ** (leng - j - 1))
        ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()   




### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n=int(input())
A=[[]for i in range(n)]
A[0].append(1)
for i in range(2,n+1):
  for j in range(i-1):
    A[i-1].append(A[i-2][j]*i)
  A[i-1].append(A[i-1][-1]+A[i-2][0])
X=list(map(int,input().split()))
Y=[X[1]-X[0]]
for i in range(2,n):
  Y.append(X[i]-X[i-1])
ans=0
for i in range(n-1):
  ans=(ans+A[n-2][i]*Y[i])%(10**9+7)
print(ans)


### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
a=1
B=[1,1]
mod=10**9+7
for i in range(2,n):
  a=a*i%mod
  B.append(pow(i,mod-2,mod))
d=[0]*(n-1)
for i in range(n-1):
  d[i]=x[i+1]-x[i]
D=[d[-1]]
for i in range(n-2):
  D.append(D[-1]+d[-2-i])
D=D[::-1]
ans=0
for i in range(n-1):
  ans=(ans+D[i]*a*B[i+1])%mod
print(ans)
### BUGGY CODE ###

import sys 

readline = sys.stdin.readline 

N = int(input())
X = list(input())

def popcount(number):
    num = number
    counter = 0
    while num != 0:
        one_bit = bin(num)[2:].count('1')
        num = num % one_bit
        counter += 1

    return counter

for i in range(N):
    # ビットの反転
    x_copy = X.copy()   
    if x_copy[i] == '0':
        x_copy[i] = '1'
    else:
        x_copy[i] = '0'

    bit_int = int("".join(x_copy), 2)

    print(popcount(bit_int))






### FIXED CODE ###

def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(input())
    X = readline()
    bit_count = X.count('1')
    mod1 = int(X, 2) % (bit_count + 1)
    mod2 = int(X, 2) % (bit_count - 1) if (bit_count - 1) != 0 else 0

    for i in range(N):
        if X[i] == '0':
            X_rest = (mod1 + pow(2, N - 1 - i, bit_count + 1)) % (bit_count + 1)
        else:
            if bit_count - 1 != 0:
                X_rest = (mod2 - pow(2, N - 1 - i, bit_count - 1)) % (bit_count - 1)
            else:
                print(0)
                continue

        counter = 1
        while X_rest != 0:
            X_rest = popcount(X_rest)
            counter += 1
        print(counter)
### BUGGY CODE ###

n = int(input())
c = input()

ans = n
for i in range(n+1):
    a = c[:i].count("W")
    b = c[i:].count("R")
    ans = min(ans,max(a,b))

print(ans)

### FIXED CODE ###

n = int(input())
c = list(input())

ans = 0

r = c.count("R")
for i in range(r):
    if c[i] == "W":
        ans+=1
print(ans)
### BUGGY CODE ###

n = input()
n = int(n)
p = list(map(float,input().split()))

l = [0]*(n+1)
l[0] = (1-p[0])
l[1] = p[0]

for i in range(n-1):
    t = [0]*(n+1)
    t[0] = l[0]*(1-p[i+1])
    for j in range(1,n+1):
        t[j] = l[j]*(1-p[i+1]) + l[j-1]*p[i+1]
    l = t

## 制約：Nは奇数
l.reverse()
print(sum([l[i] for i in range((n+1)//2)]))


### FIXED CODE ###

n = input()
n = int(n)
p = list(map(float,input().split()))

l = [1]

for i in range(n):
    t1 = [j*(1-p[i]) for j in l]
    t1.append(0)
    t2 = [0]+[j*p[i] for j in l]
    l = [t1[j] + t2[j] for j in range(len(t1))]

l.reverse()
print(sum([l[i] for i in range((n+1)//2)]))
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    while i < N :
        if None not in ANS[i:i+L] :
            i += L
            continue
        ANS[i] = min(Whole[i+1-L:i+1])
        i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

N=input()

lists = []
temp=[i for i in range(10)]

dic={0:1}

for i in N:
    new_dic={}
    if i == "?":
        for amari,count in list(dic.items()):
            for num in temp:
                a = (amari*10 + num) % 13
                if a in new_dic:
                    new_dic[a]+=count
                else:
                    new_dic[a]=count
    else:
        num=int(i)
        for amari,count in list(dic.items()):
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    dic = new_dic

try:
    print(dic[5]%(10**9 + 7))
except:
    print(0)

### FIXED CODE ###


N=input()

lists = []
temp=[i for i in range(10)]

MOD=10**9+7

dic={0:1}

for i in N:
    new_dic={}
    hoge=list(dic.items())
    if i == "?":
        for amari,count in hoge:
            amari*=10
            for num in temp:
                a = (amari + num) % 13
                if a in new_dic:
                    new_dic[a]+=count
                else:
                    new_dic[a]=count
    else:
        num=int(i)
        for amari,count in hoge:
            a = (amari*10 + num)%13
            if a in new_dic:
                new_dic[a]+=count
            else:
                new_dic[a]=count
    for key in new_dic:
        new_dic[key] %= MOD
    dic = new_dic

try:
    print(dic[5])
except:
    print(0)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    
    BL = (300000).bit_length()
    WIDTH = pow(2, BL)
    BUFSIZE = pow(2, BL+1) - 1
    BASE = BUFSIZE - WIDTH
    
    # TODO: default value
    buf = [0] * BUFSIZE
    
    def update(i, x):
        i += BASE
        buf[i] = x
        i = (i-1) // 2
        while i >= 0:
            buf[i] = compare(buf[2*i+1], buf[2*i+2])
            i = (i-1) // 2
    
    # [q_left, q_right]
    def search(q_left, q_right):
        return _search(0, WIDTH, 0, q_left, q_right)
    
    def _search(l, width, i, q_left, q_right):
        if q_right < l or l + width - 1 < q_left:
            return 0
        if q_left <= l and l + width - 1 <= q_right:
            return buf[i]
        nwidth = width // 2
        c1 = _search(l, nwidth, 2*i+1, q_left, q_right)
        c2 = _search(l+nwidth, nwidth, 2*i+2, q_left, q_right)
        return compare(c1, c2)
    
    def compare(i1, i2):
        if i1 > i2:
            return i1
        else:
            return i2
    
    for _ in range(N):
        a = int(input())
        maxlen = search(a-K, a+K)
        update(a, maxlen+1)
    print(search(0, 300000))

main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())

BL = (300001-1).bit_length()
WIDTH = pow(2, BL)
BUFSIZE = pow(2, BL+1) - 1
BASE = BUFSIZE - WIDTH
DEFAULT = 0

buf = [DEFAULT] * BUFSIZE

def update(i, x):
    i += BASE
    buf[i] = x
    i = (i-1) // 2
    while i >= 0:
        buf[i] = compare(buf[2*i+1], buf[2*i+2])
        i = (i-1) // 2

# [q_left, q_right]
def search(left, right):
    ansl = ansr = DEFAULT
    left += BASE
    right += BASE
    while left < right:
        if not (left & 1):
            ansl = compare(ansl, buf[left])
            left += 1
        if right & 1:
            ansr = compare(ansr, buf[right])
            right -= 1
        left = (left-1) // 2
        right = (right-1) // 2
    if left == right:
        ansl = compare(ansl, buf[left])
    return compare(ansl, ansr)

def compare(v1, v2):
    return v1 if v1 > v2 else v2

for _ in range(N):
    a = int(input().rstrip())
    maxlen = search(max(0, a-K), min(a+K, 300000))
    update(a, maxlen+1)
print(search(0, 300000))
### BUGGY CODE ###

N, M = map(int, input().split())
L = [0] * N
D = {}
c = 1
for i in range(M):
  A, B = map(int, input().split())
  if L[A - 1] == L[B - 1] == 0:
    D[c] = set()
    D[c].add(A)
    D[c].add(B)
    L[A - 1] = c
    L[B - 1] = c
    c += 1
  elif L[A - 1] == 0:
    D[L[B - 1]].add(A)
    L[A - 1] = L[B - 1]
  elif L[B - 1] == 0:
    D[L[A - 1]].add(B)
    L[B - 1] = L[A - 1]
  elif L[A - 1] != L[B - 1]:
    D[L[A - 1]] |= D[L[B - 1]]
    for j in D.pop(L[B - 1]):
      L[j - 1] = L[A - 1]
  #print(L, D, sep = "\n")
print(len(D) + L.count(0) - 1)

### FIXED CODE ###

N, M = map(int, input().split())
L = [0] * N
D = {}
c = 1
for i in range(M):
  A, B = map(int, input().split())
  if L[A - 1] == L[B - 1] == 0:
    D[c] = set()
    D[c].add(A)
    D[c].add(B)
    L[A - 1] = c
    L[B - 1] = c
    c += 1
  elif L[A - 1] == 0:
    D[L[B - 1]].add(A)
    L[A - 1] = L[B - 1]
  elif L[B - 1] == 0:
    D[L[A - 1]].add(B)
    L[B - 1] = L[A - 1]
  elif L[A - 1] != L[B - 1]:
    if len(D[L[A - 1]]) < len(D[L[B - 1]]):
      A, B = B, A
    D[L[A - 1]] |= D[L[B - 1]]
    for j in D.pop(L[B - 1]):
      L[j - 1] = L[A - 1]
  #print(L, D, sep = "\n")
print(len(D) + L.count(0) - 1)
### BUGGY CODE ###

Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]+[0]*N
for i in range(1,N+1):
    if i in a:
        continue
    if i == 1:
        b[1] += b[0]
        continue
    b[i] += b[i-1]+b[i-2]
    if b[i] > Mod:
        b[i] %= Mod
print(b[N])

### FIXED CODE ###

Mod = 10**9+7
N,M = map(int, input().split())
a = [int(input()) for _ in range(M)]
b = [1]*(N+1)
for j in a:
    b[j] = 0
for i in range(1,N+1):
    if b[i] == 0:
        continue
    if i == 1:
        b[1] = 1
        continue
    b[i] = b[i-1]+b[i-2]
    if b[i] >= Mod:
        b[i] %= Mod
print(b[N])