Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
import sys

def maybe_check(n,A):
    if n <= 0 or n >= 10000:
        return False

    if len(A) <= 0 or len(A) > n:
        print len(A),n-1
        return False

    maybe_list = []
    for i in range(1, n+1):
        left = abs(i - n)
        right = (n -1 )- left
        maybe_list.append(abs(left - right))

    pattern =  len(set([x for x in maybe_list if maybe_list.count(x) != 1]))

    for i in A:
        if i in maybe_list:
            maybe_list.remove(i)
        else:
            return 0

    return (2 ** pattern) % div



args = sys.argv
n = int(args[1])
A = map(int,args[2:])

div = 10 ** 9 + 7
print maybe_check(n,A)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import Counter

def maybe_check(n,A):
    try:
        if n <= 0 or n > 100000:
            raise

        div = 1000000007
        maybe_list = [abs(abs(i - n) - ((n -1 ) - abs(i - n))) for i in range(1, n+1)]
        maybe_list.sort()
        A.sort()
        if A !=  maybe_list:
            raise

        pattern = len([num for num,count in Counter(maybe_list).items() if count != 1])
        return (2 ** pattern) % div

    except:
        return 0


_n = int(raw_input())
_A = map(int,raw_input().split())

print maybe_check(_n,_A)
# ########## ------ Import ------- ##########

import sys
import math
from collections import Counter
from collections import deque as deq
from functools import lru_cache

# ########## ------ Define -------- #########

INT_MAX = float("inf")
INT_MIN = float("-inf")

# ########## ------ Input Functions ---- #########

input = sys.stdin.readline


def inp():
    return(int(input()))


def inlt():
    return(list(map(int, input().split())))


def insr():
    s = input()
    return(list(s[:len(s) - 1]))


def invr():
    return(map(int, input().split()))


# ########## ------ Code ------- ##########
def go(i):
    if i == 0:
        dp[i] = 0
        return dp[i]
    if i == 1:
        dp[i] = abs(a[0] - a[i])
        return dp[i]

    if dp[i] != -1:
        return dp[i]

    dp[i] = min(abs(a[i] - a[i - 1]) + go(i - 1),
                abs(a[i] - a[i - 2]) + go(i - 2))
    return dp[i]


t = inp()
a = inlt()
dp = [-1] * (t)
if t == 1:
    print(0)
elif t == 2:
    print(abs(a[0] - a[i]))

else:
    dp[0] = 0
    dp[1] = abs(a[0] - a[1])
    for i in range(2, t):
        dp[i] = min(abs(a[i] - a[i - 1]) + dp[i - 1],
                    abs(a[i] - a[i - 2]) + dp[i - 2])


print(dp[t - 1])


### FIXED CODE ###

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

dp = [0] * n
dp[1] = abs(arr[1] - arr[0])

for i in range(1, n - 1):
    dp[i + 1] = min(dp[i - 1] + abs(arr[i + 1] - arr[i - 1]), dp[i] + abs(arr[i + 1] - arr[i]))

print(dp[-1])
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()

def fanc(n, a):
    if n == 1: 
        print(1)
        return 0
    cnt = 0
    while len(a) > 0:
        same_cnt = 1
        j = 1
        while a[0] == a[j]:
            same_cnt += 1
            if j == len(a) - 1:
                break
            j += 1
        if same_cnt  % 2 == 1:
            cnt += 1
        del a[0:same_cnt]
    print(cnt)
    return 0

fanc(n, a)


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()

def fanc(n, a):
    if n == 1: 
        print(1)
        return 0
    cnt = 0
    while len(a) > 1:
        same_cnt = 0
        j = 1
        while a[0] == a[j]:
            same_cnt += 1
            if j == len(a) - 1:
                break
            j += 1
        if same_cnt  % 2 == 0:
            cnt += 1
        del a[0:same_cnt+1]
    if len(a) == 1: cnt += 1
    print(cnt)
    return 0

fanc(n, a)
import math
n = int(input())
X = list(map(int, input().split()))
a = sum(X)
b = sum(X[i]**2 for i in range(n))
m = math.floor(a/n)
if m + 1/2 <= a/n:
  m += 1
else:
  break
s = n*(m**2) - 2*a*m + b
print(s)

### FIXED CODE ###

import numpy as np
n = int(input())
X = list(map(int, input().split()))
a = sum(X)
b = sum(X[i]**2 for i in range(n))
m = np.floor(a/n)
if m + 1/2 <= a/n:
  m += 1
s = n*(m**2) - 2*a*m + b
print(int(s))
import sys
k=int(input())
n0 =input().split()
n=list(map(int,n0))
a=[]
for i in range(k-1,-1,-1):
    a.append(n[i])
for i in a:
    if i == a[k-1]:
        print(str(i))
    else:
        print(str(i)+' ', end="")
            

### FIXED CODE ###

raw_input()
l = raw_input().split()
l.reverse()
print " ".join(l)
mod=998244353
N,A,B,K=map(int,input().split())
 
#繰り返し二乗法
def great_power(x, y):
    if   y == 0:
      return 1
    elif y == 1:
      return x % mod
    elif y % 2 == 0:
      return great_power(x, y//2)**2 % mod
    else:
      return great_power(x, y//2)**2 * x % mod

#階乗計算
factorial=[1]
for i in range(1,N+1):
    factorial.append(factorial[i-1]*i %mod)

#逆元計算
inverse=[0]*(N+1)
inverse[N] = great_power(factorial[N], mod-2)
for i in range(N-1, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod

#combination計算
def nCr(n,r):
  if n==r or n<r:
    return 1
  return factorial[n] * inverse[r] * inverse[n-r] % mod

ans=[]
for i in range(N+1):
  if (K-A*i)%B==0:
    ans.append((i,(K-A*i)//B))

out=0
for x,y in ans:
  out+=(nCr(N,x)*nCr(N,y))%mod
print(out%mod)

### FIXED CODE ###

mod=998244353
N,A,B,K=map(int,input().split())
 
#繰り返し二乗法
def great_power(x, y):
    if   y == 0:
      return 1
    elif y == 1:
      return x % mod
    elif y % 2 == 0:
      return great_power(x, y//2)**2 % mod
    else:
      return great_power(x, y//2)**2 * x % mod

#階乗計算
factorial=[1]
for i in range(1,N+1):
    factorial.append(factorial[i-1]*i %mod)

#逆元計算
inverse=[0]*(N+1)
inverse[N] = great_power(factorial[N], mod-2)
for i in range(N-1, -1, -1):
    inverse[i] = inverse[i+1] * (i+1) % mod

#combination計算
def nCr(n,r):
  if n==r or n<r or r==0:
    return 1
  return factorial[n] * inverse[r] * inverse[n-r] % mod

ans=0

for i in range(N+1):
  if (K-A*i)%B==0 and (K-A*i)>=0:
    j=(K-A*i)//B
    if j <= N:
      ans+=( nCr(N,i) * nCr(N,j) ) %mod
      ans %= mod

print(ans)
s = input()
print("{}".format(700 + s.count(o)))

### FIXED CODE ###

s = list(input())
t = 700 + s.count("o") * 100
print(t)
import math
A, B = map(int, input().split())
print(A * B // math.gcd(A, B))

### FIXED CODE ###

import fractions
A,B=map(int, input().split())
f=fractions.gcd(A,B)
f2=A*B//f
print(f2)
import sys

in1 = sys.stdin.readlines()
N = in1[0]
#N = 10 ** 18
#N = 2
"""
0 + 0 = 0
0 x 0 = 0

1 + 0 = 1
1 x 0 = 1

2 + 0 = 2
2 x 0 = 2
1 + 1 = 2
1 x 1 = 0

3 + 0 = 3
3 x 0 = 3
2 + 1 = 3
2 x 1 = 3
"""
p = 10 ** 9 + 7

def f(n):
    if n in d:
        return d[n]
    d[n] = f(n // 2) + f((n - 1) // 2) + f((n - 2) // 2)
    return d[n]

d = {0: 1, 1: 2}
print(f(N) % p)


### FIXED CODE ###

import sys

in1 = sys.stdin.readlines()
N = int(in1[0])
#N = 10 ** 18
#N = 2
"""
0 + 0 = 0
0 x 0 = 0

1 + 0 = 1
1 x 0 = 1

2 + 0 = 2
2 x 0 = 2
1 + 1 = 2
1 x 1 = 0

3 + 0 = 3
3 x 0 = 3
2 + 1 = 3
2 x 1 = 3
"""
p = 10 ** 9 + 7

def f(n):
    if n in d:
        return d[n]
    d[n] = f(n // 2) + f((n - 1) // 2) + f((n - 2) // 2)
    return d[n]

d = {0: 1, 1: 2}
print(f(N) % p)
n = int(input())
a = [int(x) for x in input().split()]

c = 0

for i in range(n - 1):
    minj = i
    for j in (i + 1, n):
        if a[j] < a[minj]:
            minj = j
    if minj != i:
        tmp = a[i]
        a[i] = a[minj]
        a[minj] = tmp
        c += 1

print(" ".join([str(x) for x in a]))
print(c)

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

c = 0

for i in range(n - 1):
    minj = i
    for j in range(i + 1, n):
        if a[j] < a[minj]:
            minj = j
    if minj != i:
        tmp = a[i]
        a[i] = a[minj]
        a[minj] = tmp
        c += 1

print(" ".join([str(x) for x in a]))
print(c)
n = input()
print(s.translate(str.maketrans({'1':'9','9':'1'})))

### FIXED CODE ###

n = list(input())
i = 0

while i < 3:
    if n[i] == '1':
        n[i] = '9'
        i = i + 1
    else:
        n[i] = '1'
        i = i + 1

print(''.join(n))
from collections import deque
from copy import deepcopy

length,kaisu=map(int,input().split())
A=deque(map(int,input().split()))
maxhist=[0]
for left in range(kaisu+1):
  for right in range(kaisu-left+1):
    l=deepcopy(A)
    point=[]
    dropable=kaisu-left-right
    for i in range(left):
      num=l.popleft()
      point.append(num)
    for j in range(right):
      num2=l.pop()
      point.append(num2)
    droptime=0
    while(droptime<dropable):
      if point==[]:
        break
      elif min(point)>0:
        break
      else:
        point.sort(reverse=True)
        point.pop(-1)
        droptime+=1
    maxhist.append(sum(point))
print(max(maxhist))

### FIXED CODE ###

from collections import deque
from copy import deepcopy

length,kaisu=map(int,input().split())
A=deque(map(int,input().split()))
maxhist=[0]
for left in range(kaisu+1):
  for right in range(kaisu-left+1):
    l=deepcopy(A)
    point=[]
    dropable=kaisu-left-right
    for i in range(left):
      try:
        num=l.popleft()
        point.append(num)
      except:
        pass
    for j in range(right):
      try:
        num2=l.pop()
        point.append(num2)
      except:
        pass
    droptime=0
    while(droptime<dropable):
      if point==[]:
        break
      elif min(point)>0:
        break
      else:
        try:
          point.sort(reverse=True)
          point.pop(-1)
          droptime+=1
        except:
          break
    maxhist.append(sum(point))
print(max(maxhist))
import bisect
import sys
input=sys.stdin.readline
from collections import deque
N=int(input())

cnt=0
L=[]
for i in range(N):
    n=int(input())
    L.append(n)
#print(L)
Q=[-1,10**10]
Q=deque()
Q.appendleft(10**10)
Q.appendleft(-1)
#print(Q)
for i in range(N):
    if bisect.bisect_left(Q,L[i])==1:
        Q.insert(1,L[i])
    #elif bisect.bisect_left(Q,L[i])==len(Q)-1:
        #Q.insert(len(Q)-1,L[i])
    else:
        Q[bisect.bisect_left(Q,L[i])-1]=L[i]
#print(Q)
print(len(Q)-2)

### FIXED CODE ###

import bisect
import sys
input=sys.stdin.readline
from collections import deque
N=int(input())

cnt=0
L=[]
for i in range(N):
    n=int(input())
    L.append(n)
#print(L)
Q=[-1,10**10]
Q=deque()
#Q.appendleft(10**10)
#print(Q)
for i in range(N):
    if bisect.bisect_left(Q,L[i])==0:
        Q.appendleft(L[i])
    #elif bisect.bisect_left(Q,L[i])==len(Q)-1:
        #Q.insert(len(Q)-1,L[i])
    else:
        Q[bisect.bisect_left(Q,L[i])-1]=L[i]
#print(Q)
print(len(Q))
N, K = map(int, input().split())
l = list(map(int, input().split())
ans = 0
for i in range(len(l)):
     if l[i] >= K
         ans += 1
print(ans)
    


### FIXED CODE ###

N, K = map(int, input().split())
li = list(map(int, input().split()))
ans = 0
for i in range(N):
  if li[i] >= K:
    ans += 1
print(ans)
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

N = int(input())
#N, M = map(int, input().split())
A = list(map(int, input().split()))
#A = [int(input()) for _ in range(N)]
#ABC = [list(map(int, input().split())) for _ in range(N)]

cnt = [0] * (2 * 10 ** 5 + 1)
for a in A:
    cnt[a] += 1

if cnt[1] >= 2:
    print(0)
    exit()

if cnt[1] == 1:
    print(1)
    exit()

answer = 0
for i in range(2, 2 * 10 ** 5 + 1):
    if cnt[i] == 1:
        answer += 1
    if cnt[i] == 0:
        continue
    k = 2
    while i * k <= 2 * 10 ** 5:
        cnt[i * k] = 0
        k += 1

print(answer)
    
    
    
    
    

### FIXED CODE ###

from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

cnt = [0] * (10 ** 6 + 1)
for a in A:
    cnt[a] += 1

if cnt[1] >= 2:
    print(0)
    exit()

if cnt[1] == 1:
    print(1)
    exit()

answer = 0
for i in range(2, 10 ** 6 + 1):
    if cnt[i] == 1:
        answer += 1
    if cnt[i] == 0:
        continue
    k = 2
    while i * k <= 10 ** 6:
        cnt[i * k] = 0
        k += 1

print(answer)
i = j = x = y = 0

while i >= 0:
  line = input()
  while line[j] != ' ':
    x = x + line[j]
    j += 1
  while j < len(line):
    y = y + line[j]
    j += 1

  x = int(x)
  y = int(y)

  if x == 0 and y == 0:
    break

  if x >= y:
    print(y,end=' ')
    print(x)

  else:
    print(x,end=' ')
    print(y) 

### FIXED CODE ###

x = ''
y = ''
 
while True:
  line = input()
  line = line.split()
  x = int(line[0])
  y = int(line[1])
 
  if x == 0 and y == 0:
    break
 
  if x >= y:
    print(y,end=' ')
    print(x)
 
  else:
    print(x,end=' ')
    print(y)
a = [input(),input(),input()]
l = [len(a[0]),len(a[1]),len(a[2])]
ans = l[0]+l[1]+l[2]

def check(a0, l0, a1, l1, delta):
    # stt1 >= stt0, stt1 - stt0 >=l0 must return True
    i = delta
    j = 0
    while (i<l0) and (j<l1):
        if a0[i] != a1[j]:
            if a0[i] != '?' and a1[j] != '?':
                return False
        i += 1
        j += 1
    return True

memo = [[[1]*4000 for i in range(3)] for j in range(3)]
comb2 = [(0,1),(1,0),(1,2),(2,1),(0,2),(2,0)]
for x, y in comb2:
    me = memo[x][y]
    a0, a1 = a[x],a[y]
    l0, l1 = l[x],l[y]
    for delta in range(0,l0):
        if not check(a0,l0, a1,l1, delta):
            me[delta] = 0

comb = [(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]
for i,j,k in comb:
    l0, l1, l2 = l[i],l[j],l[k]
    stt0 = 0
    for stt1 in range(0,l0+1):
        if not memo[i][j][stt1-stt0]:
            continue
        l01 = max(l0,stt1+l1)
        for stt2 in range(stt1,l01+1):
            if not memo[j][k][stt2-stt1]:
                continue
            if not memo[i][k][stt2-stt0]:
                continue
            l012 = max(l01,stt2+l2)
            ans = min(ans,l012)
print(ans)

### FIXED CODE ###

A =  [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(A[k-1])
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

a, b, c ,d = map(int, input().split())
e = lcm(c, d)
wareru = (int(b/c) + int(b/d) - int(b/e) - (int((a-1)/c) + int((a-1)/d) - int((a-1)/e)))
print(b-a+1-wareru)

### FIXED CODE ###

a, b, c ,d = map(int, input().split())
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
      return a*b//gcd(a,b)
e = lcm(c, d)
wareru = b//c + b//d - b//e - ((a-1)//c + (a-1)//d - (a-1)//e)
print(b-a+1-wareru)
N, K = map(int, input().split())
S = set()

MOD = 998244353
for _ in range(K):
    L, R = map(int, input().split())
    S |= set(range(L, R + 1))
# print(f'{S=}')

DP = [-1] * ((N + 1) * 2)
DP[0] = 0
DP[1] = 1


def f(idx):
    ans = 0
    for s in S:
        if idx - s < 0:
            continue
        if DP[idx - s] == -1:
            DP[idx - s] = f(idx - s)
        ans += DP[idx - s]
    return ans % MOD


ans = f(N)
# print(f'{DP=}')
print(ans)
# # 配るDP
# for i in range(1, N + 1):
#     for s in S:
#         DP[i + s] += DP[i]
#     print(f'{DP=}')
#     DP[i] %= MOD
# print(DP[N])


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353
LR = []
for _ in range(K):
    L, R = map(int, input().split())
    LR.append((L, R))
# print(f'{LR=}')

DP = [0] * (N + 1)
DP[1] = 1
S = [0] * (N + 1)

for i in range(1, len(DP)):
    for L, R in LR:
        v = S[max(i - L, 0)] - S[max(i - R - 1, 0)]
        DP[i] += v
    DP[i] %= MOD
    S[i] = (S[i - 1] + DP[i]) % MOD

# print(f'{DP=}')
# print(f'{S=}')
print(DP[-1])
x=1
while True:
    i=input()
    print('case {}: {}'.format(x,i))
    x+=1


### FIXED CODE ###

import sys
 
i=1
for s in sys.stdin:
  n = int(s)
  if n == 0:
    break
  print("Case ",i,": ",n,sep="")
  i += 1
N = int(input())
lis = [0]*N
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            ans = x**2 + y**2 + z**2 + x*y + y*z + z*x -1
            if ans > N:
                pass
            else:
                lis[ans] += 1
for i in range(N):
    print(lis[i])

### FIXED CODE ###

N = int(input())
lis = [0]*N
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            ans = x**2 + y**2 + z**2 + x*y + y*z + z*x -1
            if ans >= N:
                pass
            else:
                lis[ans] += 1
for i in range(N):
    print(lis[i])
N,M = map(int,input().split())

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

for i in range(N-M+1):
    for h in range(N-M+1):
        cnt = 0
        for k in range(M):
            for j in range(M):
                if A[i+k][h+j] != B[k][h]:
                    cnt += 1
        if cnt == 0:
            break
if cnt == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

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

ans = 0
for i in range(N-M+1):
    for h in range(N-M+1):
        cnt = 0
        for k in range(M):
            for j in range(M):
                if A[i+k][h+j] != B[k][j]:
                    cnt += 1
        if cnt == 0:
            ans += 1
if ans != 0:
    print("Yes")
else:
    print("No")
import statistics
import math
a,b,c,d = map(int,input().split())	
lcm = c * d // math.gcd(c, d)
#print(lcm)
def divisor(x):
	
	x_c = math.floor(x/c)
	x_d = math.floor(x/d)
	#print(x_c,x_d)
	x_lcm = math.floor(x/lcm)
	#print(x_c,x_d,x_lcm)
	return x-x_c-x_d+x_lcm
#print(divisor(b),divisor(a))
ans = divisor(b)-divisor(a-1)
print(ans)

### FIXED CODE ###


import fractions
a,b,c,d = map(int,input().split())	
lcm = c * d // fractions.gcd(c, d)
#print(lcm)
def divisor(x):
	
	x_c = x//c
	x_d = x//d
	#print(x_c,x_d)
	x_lcm = x//lcm
	#print(x_c,x_d,x_lcm)
	return x-x_c-x_d+x_lcm
#print(divisor(b),divisor(a))
ans = divisor(b)-divisor(a-1)
print(ans)
import sys
import collections

b=[]
n = map(int, raw_input().split())
a = map(int, raw_input().split())

while True:
    a.sort()

    if a[0]==a[-1]:
        print(a[0])
        break

    elif:
        for n, x in enumerate(a):
            n=n%a[0]
            if n!=0:
                b.append(n)
        a=[a[0]]
        a.extend(b)


### FIXED CODE ###

import sys
import collections

b=[]
n = map(int, raw_input().split())
a = map(int, raw_input().split())

while True:
    a.sort()
    b=[]
    if a[0]==1:
        print(1)
        break
    elif a[0]==a[-1]:
        print(a[0])
        break
    else:
        for n in a:
            n=n%a[0]
            if n!=0:
                b.append(n)
        a=[a[0]]
        a.extend(b)
n=int(input())
a=list(map(int,input().split()))
b=[0]*(n+1)
for i in a:
  if i!=0:b[i-1]+=1
  b[i]+=1
  if i!=n:b[i+1]+=1
print(max(b))

### FIXED CODE ###

n,a=int(input()),list(map(int,input().split()));c=[0]*(max(a)+1)
for i in a:
  if i>0:c[i-1]+=1
  if i<len(c)-1:c[i+1]+=1
  c[i]+=1
print(max(c))
# Segment Treeを使う。一点更新，区間最大値

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

seglen = 1 << 19

segtree = [0 for _ in range(seglen * 2)]
# segtree[seglen + i] = Bの最後の値に i を使う時のlongest len

def segset(ind, val):
    segtree[ind] = val
    ind //= 2
    while ind != 0:
        segtree[ind] = max(segtree[ind*2], segtree[ind*2 + 1])
        ind //= 2
    return


def segmax(l, r):
    ret = 0

    while l < r:

        if l % 2 == 1:
            ret = max(ret, segtree[l])
            l += 1
        l //= 2

        if r % 2 == 1:
            ret = max(ret, segtree[r - 1])
            r -= 1
        r //= 2

    return ret

A = []
for _ in range(N):
    a = int(input())
    a -= 1
    A.append(a)

ans = 0

for a in A:
    a_ind = seglen + a

    l = max(seglen, a_ind - K)
    r = min(seglen + 4000000, a_ind + K + 1)

    longest = segmax(l, r)

    segset(a_ind, longest + 1)

    ans = max(ans, longest + 1)

print(ans)

### FIXED CODE ###

# Segment Treeを使う。一点更新，区間最大値

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

seglen = 1 << 19

segtree = [0 for _ in range(seglen * 2)]
# segtree[seglen + i] = Bの最後の値に i を使う時のlongest len

def segset(ind, val):
    segtree[ind] = val
    ind //= 2
    while ind != 0:
        segtree[ind] = max(segtree[ind*2], segtree[ind*2 + 1])
        ind //= 2
    return


def segmax(l, r):
    ret = 0

    while l < r:

        if l % 2 == 1:
            ret = max(ret, segtree[l])
            l += 1
        l //= 2

        if r % 2 == 1:
            ret = max(ret, segtree[r - 1])
            r -= 1
        r //= 2

    return ret

A = []
for _ in range(N):
    a = int(input())
    A.append(a)

ans = 0

for a in A:
    a_ind = seglen + a

    l = max(seglen, a_ind - K)
    r = min(seglen + 400000, a_ind + K + 1)

    longest = segmax(l, r)

    segset(a_ind, longest + 1)

    ans = max(ans, longest + 1)

print(ans)
N=int(input())
List=list(map(int,input().split()))
count=1
for i in range(1,N):
    for j in range(i):
        w=0
        if List[j]>List[i]:
            w+=1
    if w==0:  
        count+=1
print(count)
   
    

### FIXED CODE ###

N=int(input())
List=list(map(int,input().split()))
count=1

for i in range(1,N):
    W=0
    for j in range(i):
        if List[j]>List[i]:
            W+=1
    if W==0:  
        count+=1
print(count)
youbi = ['SUN','MON','TUE','WED','THU','FRI','SAT']
y = input()

for i in range(1, 7):
  if y = youbi[i]:
    print(7-i)

### FIXED CODE ###

youbi = ['SUN','MON','TUE','WED','THU','FRI','SAT']
y = input()

for i in range(7):
  if y == youbi[i]:
    print(7-i)
A,B = int(input().split())
print(A*B)

### FIXED CODE ###

A,B = input().split()
print(int(A)*int(B))
s=input()
s[3]=str(8)
print(s)

### FIXED CODE ###

s=list(input())
s[3]="8"
ans=""
for i in range(len(s)):
  ans+=s[i]
print(ans)
print(int(input())*6.283)


### FIXED CODE ###

n,m = map(int,input().split())
s = sum(map(int,input().split()))
print(max([n-s,-1]))
a,b,c=map(int, input.split())
print(str(a b c))

### FIXED CODE ###

x,y,z=map(int,input().split())
print(str(z)+" "+str(x)+" "+str(y))
def fact(num):
  ret=[]
  if num==2:
    ret=[2]
    return ret
  elif num==3:
    ret=[2,3]
    return ret
  while 1:
    for i in range(2,int(num**0.5)+1):
      if num%i==0:
        ret.append(i)
        num=num%i
        break

n=int(input())
ans=fact(n)
print('{}: {}'.format(n,' '.join(map(str,ans)))


### FIXED CODE ###

def prime(num):
    if num==1:
        return False
    elif num==2 or num==3:
        return True
    else:
        for i in range(2,int(num**0.5)+1):
            if num%i==0:
                return False
        else:
            return True

n=int(input())
tmp=n
plist=[]
if prime(n):
    print('{}: {}'.format(n,n))
else:
    while 1:
        for i in range(2,tmp+1):
            if tmp%i==0:
                plist.append(i)
                tmp=tmp//i
                break
        else:
            break
    print('{}: {}'.format(n,' '.join(map(str,plist))))