Harryxun/stf_run huggingface dataset:
N = int(input())
A = list(map(int, input().split()))


diff = [A[i+1] - A[i] for i in range(N-1) if A[i+1]-A[i] != 0]
ans = 1
prev = diff[0]
id = 0
while(id < len(diff)-2):
    if (diff[id]*diff[id+1]) < 0:
        ans += 1
        id += 2
    else:
        id += 1

if diff[-1]*diff[-2] < 0 and diff[-2]*diff[-3]:
    ans += 1
print(ans)


### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
flag=0
ans=1
for i in range(1,N):
  if flag== 0:
    if a[i]>a[i-1]:
      flag=1
      continue
    elif a[i]<a[i-1]:
      flag=-1
      continue
    else:
      continue
  elif flag>0:
    if a[i]<a[i-1]:
      ans+=1
      flag=0
  else:
    if a[i]>a[i-1]:
      ans+=1
      flag=0
print(ans)
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(input())

N = gete(int)

cur = [0] * 3

for _ in range(N):
    a, b, c = geta(int)
    prev = cur.copy()
    cur[0] = max(prev[1], prev[2]) + a
    cur[1] = max(prev[2], prev[0]) + b
    cur[2] = max(prev[0], prev[1]) + c

print(max(cur))


### FIXED CODE ###

N = int(input())
act = []
for _ in range(N):
    act.append(tuple(map(int, input().split())))

dp = [[0]*3 for _ in range(N)]

for i in range(3):
    dp[0][i] = act[0][i]

for i in range(1, N):
    for j in range(3):
        dp[i][j] = max(dp[i-1][(j+1) % 3], dp[i-1][(j+2) % 3]) + act[i][j]


print(max(dp[N-1]))
val = input().split()
if val[1] == "+":
    print(int(val[0]+int(val[2])))
else:
    print(int(val[0] - int(val[2])))

### FIXED CODE ###

val = input().split()
if val[1] == "+":
    print(int(val[0])+int(val[2]))
else:
    print(int(val[0]) - int(val[2]))
N, A = map(int, input().split())  # N枚数のカード, 平均をAにしたい
X = list(map(int, input().split()))  # N枚のカードの中身

dp = [[[0]*(max(X)*N+2) for _ in range(N+2)] for _ in range(N+2)]

dp[0][0][0] = 1  # 0枚の中から0枚選んで合計が0になる選び方が1通りある

for i in range(N):
    now_card = X[i]
    for j in range(N+1):
        for s in range(max(X)*N+1):
            if s >= now_card:  # 今見ているのはX[i], これをどうするかで遷移先を変更する
                dp[i+1][j+1][s] += dp[i][j][s-now_card]  # 追加する余裕がある場合は追加する
            dp[i+1][j][s] += dp[i][j][s]  # 何も追加しない
ans = 0
for i in range(1, N+1):
    ans += dp[N][i][i*A]
print(ans)


### FIXED CODE ###

N, A = map(int, input().split())  # N枚のカード, 平均をAにしたい

X = tuple(map(int, input().split()))  # カードリスト

# [カードの総枚数][選んだカードの枚数][今の総和]
dp = [[[0]*(50*N+1) for _ in range(N+1)] for _ in range(N+1)]

# 0枚の中から0枚選んで総和が0になるパターンは1つ
dp[0][0][0] = 1

for i in range(N):
    for j in range(N+1):
        for k in range(N*50+1):
            if dp[i][j][k]:  # 今の状態を未来へ遷移させる処理
                dp[i+1][j][k] += dp[i][j][k]  # 何も加えず未来へ
                dp[i+1][j+1][k+X[i]] += dp[i][j][k]  # 今見ているカードを加えて未来に遷移

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

print(ans)
N, K = map(int, input().split())
S = input()

print(S[1:K] + {'A': 'a', 'B': 'b', 'C': 'c'}[S[K]] + (S[K+1:] if K+1 < N else ''))

### FIXED CODE ###

N, K = map(int, input().split())
S = input()
K -= 1
print(S[:K] + {'A': 'a', 'B': 'b', 'C': 'c'}[S[K]] + (S[K+1:] if K+1 < N else ''))
n , y = map(int,input().split())
y = y//1000
m = 0
for i in range(y//10+1):
    y1 = y-10*i - n +i
    if y1%4 == 0:
    if n-i-y1//4>=0:
        print(i,y1//4,n-i-y1//4)
        exit()
print('-1 -1 -1')

### FIXED CODE ###

n , y = map(int,input().split())
y = y//1000
for i in range(y//10+1):
    y1 = y-10*i - n +i
    if y1 >=0 and y1%4 == 0 and n-i-y1//4>=0:
        print(i,y1//4,n-i-y1//4)
        exit()
print('-1 -1 -1')
from collections import deque
from copy import copy

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

def gcd_of_array(_array):
    _array_copy = copy(_array)
    array_of_gcd = deque([])
    n = len(_array_copy)
    if n == 1:
        return _array[0]
    if n % 2 == 1:
        a = _array_copy.pop()
        array_of_gcd.append(a)
    for i in range(0,N-1,2):
        array_of_gcd.append(gcd(_array_copy.pop(),_array_copy.pop()))

    return gcd_of_array(array_of_gcd)

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

gcd_max=1

for i in range(N):
    a = A.popleft()
    gcd_max = max(gcd_max, gcd_of_array(A))
    A.append(a)

print(gcd_max)


### FIXED CODE ###

from collections import deque
from copy import copy
from array import array

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

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

def get_prefix_gcd_list(Adeque):
    prefix_gcd = array('i', [0]*N)
    # marker
    prefix_gcd[0] = 0
    # the first itself is gcd
    prefix_gcd[1] = Adeque.popleft()
    for i in range(2,N):
        a = Adeque.popleft()
        prefix_gcd[i] = gcd(prefix_gcd[i-1], a)
        pass
    return prefix_gcd
        
    
# PREFIX_GCD[i]...i より前の要素のGCD
PREFIX_GCD = get_prefix_gcd_list(deque(copy(A)))

# PREFIX_GCD[i]...i より後の要素のGCD
POSTFIX_GCD=list(reversed(get_prefix_gcd_list(deque(reversed(A)))))

gcd_max=1

for i in range(N):
    pre = PREFIX_GCD[i]
    pos = POSTFIX_GCD[i]
    if pre == 0:
        _gcd = pos
    elif pos == 0:
        _gcd = pre
    else:
        _gcd = gcd(pre,pos)
    gcd_max = max(gcd_max, _gcd)
        
print(gcd_max)
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n = int(input())
a = [0]*n
a = list(map(int, input().split()))
map(lambda x: x-1, a)
ty=[0]*n

for i in range(0, n):
    ty[a[i]]+=1

s = 0

for i in range(0, n):
    if ty[i]>=2:
        s += comb(ty[i], 2)

for k in range(0, n):
    if ty[a[k]]==2:
        print(s-1)
    elif ty[a[k]]>2:
        print(s-comb(ty[a[k]], 2)+comb(ty[a[k]]-1, 2))
    else:
        print(s)

### FIXED CODE ###

import random


def nC2(n):
    return int(n*(n-1)/2)

n = int(input())

a = [0]*n
a = list(map(int, input().split()))
a = [i-1 for i in a]

ty=[0]*n

for i in range(0, n):
    ty[a[i]]+=1

s = 0

for i in range(0, n):
    if ty[i]>=2:
        s += nC2(ty[i])

for k in range(0, n):
    if ty[a[k]]==2:
        print(s-1)
    elif ty[a[k]]>2:
        print(s-nC2(ty[a[k]])+nC2(ty[a[k]]-1))
    else:
        print(s)
N,A=map(int,input().split())

print(N*N-A)

### FIXED CODE ###

N=int(input())
A=int(input())

print(N*N-A)
n,m=map(int,input().split())
mis,mas=[],[]
for _ in range(m-1):
  tmp=list(map(int,input().split()))
  mis.append(tmp[0])
  mas.append(tmp[1])
ans=max(mas)-min(mis)
print(ans if ans>0 else 0)

### FIXED CODE ###

n,m=map(int,input().split())
mis,mas=[],[]
for _ in range(m):
  tmp=list(map(int,input().split()))
  mis.append(tmp[0])
  mas.append(tmp[1])
ans=min(mas)-max(mis)+1
print(ans if ans>0 else 0)
from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = [input() for i in hs]
for i in hs:
    for j in ws:
        if a[i][j] == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


hw = set(range(h*w))
for i in hw:
    d = d_list_update(d, h, w)
    if not d:
        break
ans = max([max(e) for e in memo])
print(ans)

### FIXED CODE ###

from collections import deque
 
 
h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
d = deque()
memo = [[-1] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append((i, j))
    memo[i][j] = 0
while d:
    dh, dw = d.popleft()
    for i, j in move:
        dhn, dwn = dh + i, dw + j
        if (0 <= dhn < h) and (0 <= dwn < w) and (memo[dhn][dwn] < 0):
            d.append((dhn, dwn))
            memo[dhn][dwn] = memo[dh][dw] + 1
ans = max([max(e) for e in memo])
print(ans)
L = int(input())

ans = 0
for i in range(1, L+1):
  for j in range(1, L+1):
    if L - i - j > 0:
      V = i*j*(L - i - j)
    if V > ans:
      ans = V
print(ans)

### FIXED CODE ###

L = int(input())

ans = (L**3)/27
print(ans)
n = int(input())
arr = list(map(int, input().split()))
  
cost = [0]*n
cost[0] = 0
for i in range(1, n):
  if i > 1:
    cost[i] = min(abs(arr[i]-arr[i-2])+cost[i-2], abs(arr[i]-arr[i-1])+cost[i-1])
  elif i == 1:
    cost[i] = minabs(arr[i]-arr[i-1])

print(cost[-1])

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
  
cost = [0]*n
cost[0] = 0
for i in range(1, n):
  if i > 1:
    cost[i] = min(abs(arr[i]-arr[i-2])+cost[i-2], abs(arr[i]-arr[i-1])+cost[i-1])
  elif i == 1:
    cost[i] = abs(arr[i]-arr[i-1])

print(cost[-1])
x=input()
a=input()
b=input()
print((x-a)%b)

### FIXED CODE ###

x=int(input())
a=int(input())
b=int(input())
print((x-a)%b)
import sys
from bisect import bisect_left, bisect_right


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def aggregate(self):
        stack = [1]
        ans = 0
        while stack:
            i = stack.pop()
            if self.data[i] != self.sentinel:
                ans += self.data[i] * (self.n >> i.bit_length() - 1)
                continue
            i <<= 1
            stack.append(i)
            stack.append(i + 1)
        return ans

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = list(map(int, line.split()))
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = [int(line) for line in lines[n:]]
rut = RangeUpdateTree(q * 2)
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)
data = rut.data[rut.offset:]
# rut.debug_print()
print('\n'.join(map(str, data[:q])))


### FIXED CODE ###

import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    while ss < tt:
        if skip[ss] == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = skip[ss]
print('\n'.join(map(str, ans)))
import math
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
def mon():
    input()
    a=[int(i) for i in input().split()]
    return gcd_list(a)
print(mon())

### FIXED CODE ###

from functools import reduce
import fractions
def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def mon():
    input()
    a=[int(i) for i in input().split()]
    return gcd_list(a)
print(mon())
xx=int(input())
if(x==1):
  print("Hello World")
else:
  x=int(input())
  y=int(input())
  print(x+y)


### FIXED CODE ###

x=int(input())
if(x==1):
  print("Hello World")
else:
  x=int(input())
  y=int(input())
  print(x+y)
n = int(input())
A = int(input())
B = int(input())
if n == 1:
    print("Hello World")
else:
    print(A + B)


### FIXED CODE ###

n = int(input())

if n == 1:
    print("Hello World")
if n == 2:
    a = int(input())
    b = int(input())
    print(a + b)
from sys import stdin
ma = 10**18
n = int(stdin.readline())
a = map(int,stdin.readline().split())
x = 0
s = sum(n)
for i in a[:-1]:
 x+= i
 ma  = min(ma, abs(s-2*x) )
print ma

### FIXED CODE ###

from sys import stdin
ma = 10**18
n = int(stdin.readline())
a = map(int,stdin.readline().split())
x = 0
s = sum(a)
for i in a[:-1]:
 x+= i
 ma  = min(ma, abs(s-2*x) )
print ma
n,q=map(int,input().split())
s=input()
c=[0 for _ in range(n)]
p=''
for i in range(1,n):
  x=s[i]
  if p=='A' and x='C':
    c[i-1]=1
  p=x
for i in range(q):
  ans=0
  l,r=map(int,input().split())
  ans=sum(c[l-1:r-1])
 # if s[]
  print(ans)


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
c=[0 for _ in range(n)]
p=''
d=0
for i in range(n):
  x=s[i]
  if p=='A' and x=='C':
    d+=1
  p=x
  c[i]=d
for i in range(q):
  ans=0
  l,r=map(int,input().split())
  ans=c[r-1]-c[l-1]

  print(ans)
from networkx import*;_,*n=map(str.split,open(0));print(max(map(len,[*connected_components(Graph(n))]),1,1))

### FIXED CODE ###

l=lambda:map(int, input().split())
n,m=l()
p=[-1]*n
def r(x):
  if p[x]<0:return x
  p[x]=r(p[x]);return r(p[x])
def u(x,y):
  x,y=r(x),r(y)
  if x==y: return  
  p[x]+=p[y]
  p[y]=x
def e(x,y):
  return r(x)==r(y)
def s(x):
  return -p[r(x)]
for _ in range(m):
  a,b=l()
  u(a-1,b-1)
print(-min(p))
import math
from functools import reduce

A,B,C,D = list(map(int,input().split()))
lcm = C*D/math.gcd(C,D)
a = (A-1) - ((A-1)//C + (A-1)//D - (A-1)//lcm)
b = (B) - ((B)//C + (B)//D - (B)//lcm)
print(int(b-a))

### FIXED CODE ###

from fractions import gcd

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

lcm = C*D/gcd(C,D)

a = (A-1) - ((A-1)//C + (A-1)//D - (A-1)//int(lcm))
b = (B) - ((B)//C + (B)//D - (B)//int(lcm))
print(int(b-a))
A,B = map(int, input().split())
if A > B:
  print('GREATER')
if A < B:
  print('LESS')
if A == B:
  print('EQUAL')

### FIXED CODE ###

A = int(input())
B = int(input())
if A > B:
  print('GREATER')
if A < B:
  print('LESS')
if A == B:
  print('EQUAL')
N = input()
K = input()
counter = 0
for i in range(int(N)):
    temp = int(input())
    if temp >= int(K) :
       counter = counter + 1
print(counter)

### FIXED CODE ###

N,K = map(int,input().split())
height_list = list(map(int,input().split()))
print(sum([1 for i in height_list if i >= K]))
x = raw_input().split()

y = map(int,x)

a = y[0]
b = y[1]

c = a*b
d = (a+b)*2

print c, d


### FIXED CODE ###

a, b= map(int, input().split())


c = (a*b)
d = (a+b)*2

print( c, d)
# Aizu Problem 0221: Fizz Buzz

import sys, math, os, struct

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def valid(k, a):
    if k % 3 == 0 and k % 5 == 0:
        return a == "FizzBuzz"
    elif k % 3 == 0:
        return a == "Fizz"
    elif k % 5 == 0:
        return a == "Buzz"
    else:
        return int(a) == k

    
def fizz_buzz(m, n, A):
    players = list(range(1, m + 1))
    p = 0
    k = 0
    while len(A) > 0:
        k += 1
        a = A.pop(0)
        if valid(k, a):
            p = (p + 1) % m
        else:
            if len(players) == 0:
                print()
                return
            players.pop(p)
            m -= 1
            if p == m:
                p = 0
    print(' '.join([str(p) for p in players]))
    
    
while True:
    m, n = [int(_) for _ in input().split()]
    if m == 0:
        break
    A = [input().strip() for _ in range(n)]
    fizz_buzz(m, n, A)

### FIXED CODE ###

# Aizu Problem 0221: Fizz Buzz

import sys, math, os, struct

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def valid(k, a):
    if k % 15 == 0: 
        return a == "FizzBuzz"
    elif k % 3 == 0:
        return a == "Fizz"
    elif k % 5 == 0:
        return a == "Buzz"
    else:
        return a == str(k)

    
def fizz_buzz(m, n, A):
    players = list(range(1, m + 1))
    p = 0
    k = 0
    while len(A) > 0:
        k += 1
        a = A.pop(0)
        if valid(k, a):
            p = (p + 1) % m
        else:
            if len(players) == 0:
                print()
                return
            players.pop(p)
            if len(players) == 1:
                break
            m -= 1
            p %= m
    print(' '.join([str(p) for p in players]))
    
    
while True:
    m, n = [int(_) for _ in input().split()]
    if m == 0:
        break
    A = [input().strip() for _ in range(n)]
    fizz_buzz(m, n, A)
import pandas as pd
from sys import stdin

d = pd.to_datetime( stdin.readline().strip() )
print("TBD" if (d > pd.to_datetime("2019/4/30")) else "Heisei")


### FIXED CODE ###

from sys import stdin
 
i = stdin.readline().strip()
d = tuple(map(int, i.split("/")))
print("Heisei" if d <= (2019,4,30) else "TBD")
N = int(input())
a = map(int,raw_input().split())

amax = (max(a))
amin = (min(a))

res = abs(amax-amin)
print (res) 

### FIXED CODE ###

N = int(input())

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

amax = (max(a))
amin = (min(a))

res = abs(amax-amin)
print (res)
n = int(input())
c=list(map(int, input().split())) 

n_pos = 0
max = 0
for i in c:
  if i>=max:
  	n_pos += 1
    max = i
  else:
    pass
print(n_pos)

### FIXED CODE ###

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

n_pos = 0
max_c = 0
for i in c:
    if i>=max_c:
        n_pos += 1
        max_c = i
    else:
        pass
print(n_pos)
import math

N = int(input())
h = map(int, input().split())
cost_list = [math.inf for _ in range(N)]
cost_list[0]  = 0 

for i in range(1, N):
  if cost_list[i] > (cost_list[i-1] + math.abs(h[i] - h[i-1])):
    cost_list[i] = cost_list[i-1] + math.abs(h[i]-h[i-1])
   
  if i > 1:
    if cost_list[i] > (cost_list[i-2] + math.abs(h[i] - h[i-2])):
      cost_list[i] = cost_list[i-2] + math.abs(h[i]-h[i-2])

print(cost[N-1])

### FIXED CODE ###

N = int(input())
h = list(map(int, input().split()))
cost_list = [float('inf') for _ in range(N)]
cost_list[0]  = 0

for i in range(1, N):
    if cost_list[i] > (cost_list[i-1] + abs(h[i] - h[i-1])):
        cost_list[i] = cost_list[i-1] + abs(h[i]-h[i-1])

    if i > 1:
        if cost_list[i] > (cost_list[i-2] + abs(h[i] - h[i-2])):
            cost_list[i] = cost_list[i-2] + abs(h[i]-h[i-2])

print(cost_list[N-1])
A=input()
B=input()
C=input()
D=input()
a=int(A)
b=int(B)
c=int(C)
d=int(D)

print(0)



### FIXED CODE ###



a,b,c,d=[int(i) for i in input().strip().split(' ')]

'''
入力は他の人のを見た
'''

max=0
min=0

if a < c :
    max=c
else :
    max=a
    
if b > d :
    min=d
else :
    min=b
if ( min - max ) > 0 :
    print( min - max )
else :
    print(0)
S = input()

List = ['A', 'K', 'I', 'H', 'A', 'B', 'A', 'R', 'A']
num = 0

for i in range(len(S)):
    if num > 8:
        print('NO')
        exit()
    if S[i] == List[num]:
        num += 1
    elif List[num] == 'A':
        num += 1
        if S[i] == List[num]:
            num += 1
        else:
            print('NO')
            exit()
    else:
        print('NO')
        exit()

print('YES')



### FIXED CODE ###

x = 'KIHBR'
T = []
for i in range(1<<6):
    t = ''
    for j in range(6):
        if i&(1<<j) and j != 1 and j != 2:
            t += 'A'
        if j != 5:
            t += x[j]
    T.append(t)
S = input()
if S in T:
    print('YES')
else:
    print('NO')
input = sys.stdin.readline


def acinput():
    return list(map(int, input()[:-1].split(" ")))


class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x, y: x+y, default=0):
        self.size = 2**(size-1).bit_length()  # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2)  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                # モノイドでは可換律は保証されていないので演算の方向に注意
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


def acinput():
    return list(map(int, input()[:-1].split(" ")))


N, K = acinput()

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

st = SegmentTree(N+10, f=max)

res = 0
for sa in A:
    L = max(sa-K, 0)
    R = min(sa+K, N+2)

    tmp = st.query(L, R+1)+1
    st.update(sa, tmp)
    res = max(tmp, res)

print(res)


### FIXED CODE ###



class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x, y: x+y, default=0):
        self.size = 2**(size-1).bit_length()  # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2)  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                # モノイドでは可換律は保証されていないので演算の方向に注意
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


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

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

st = SegmentTree(300000+10, f=max)

res = 0
for sa in A:
    L = max(sa-K, 0)
    R = min(sa+K, 300001)

    tmp = st.query(L, R+1)+1
    st.update(sa, tmp)
    res = max(tmp, res)

print(res)
import math

n, x0 = list(map(int, input().split()))
x = list(map(int, input().split()))

xx0 = [abs(xi-x0) for xi in x ]

y = xx0[0]
for yi in xx0:
    y = math.gcd(y, yi)
    
print(y)

### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

n, x0 = list(map(int, input().split()))
x = list(map(int, input().split()))

xx0 = [abs(xi-x0) for xi in x ]

y = xx0[0]
for yi in xx0:
    y = gcd(y, yi)
    
print(y)
A, B, C, D = input().split()
A = int(A)
B = int(B)
C = int(C)
D = int(D)

if A < C:
    if B < C:
        print(0)
    elif A <= C and D <= B:
        print(D-C)
    else:
        ptint(B-C)
else:
    if D < A:
        print(0)
    elif C <= A and N <= D:
        print(B-A)
    else:
        print(D-A)


### FIXED CODE ###

A, B, C, D = input().split()
A = int(A)
B = int(B)
C = int(C)
D = int(D)


def solve(A, B, C, D):
    if A < C:
        if B < C:
            return 0
        elif A <= C and D <= B:
            return (D - C)
        else:
            return (B - C)
    else:
        if D < A:
            return 0
        elif C <= A and B <= D:
            return (B - A)
        else:
            return (D - A)

print(solve(A, B, C, D))
import math
N, D = map(int, input().split())
person = math.cell(N / (D*2+1))
print(person)


### FIXED CODE ###

N,D = map(int,input().split())
if N % (D*2+1) != 0:
  p = N // (D*2+1) + 1
else:
  p = N // (D*2+1)
  
print(p)