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

n = int(input())
s = input()
count = 0

r = []
g = []
b = []
for i in range(n):
  if s[i] == 'R':
    r.append(i)
  elif s[i] == 'G':
    g.append(i)
  else:
    b.append(i)
    
mcount = 0
for i in range(int((n-1)/2)):
  k = i+1
  for j in range(k, n-k):
    if s[j] != s[j-k] and s[j] != s[j+k] and s[j-k] != s[j+k]:
      mcount += 1
  

for i in range(n):
  if i in r:
    for j in g:
      for k in b:
        if k < j:
          continue
        count += 1
    for j in b:
      for k in g:
        if k < j:
          continue
        count += 1      
  if i in g:
    for j in r:
      for k in b:
        if k < j:
          continue
        count += 1
    for j in b:
      for k in r:
        if k < j:
          continue
        count += 1
  if i in b:
    for j in g:
      for k in r:
        if k < j:
          continue
        count += 1
    for j in r:
      for k in g:
        if k < j:
          continue
        count += 1
  if i in r:
    r = r[1:]
  elif i in g:
    g = g[1:]
  else:
    b = b[1:]


print(count-mcount)

### FIXED CODE ###

n = int(input())
s = input()
r = []
g = []
b = []

ans = s.count("R")*s.count("G")*s.count("B")

for i in range(n):
    for j in range(i+1,n):
        k = 2*j-i
        if k>=n:
          break
        ans -= s[k] != s[i] != s[j] != s[k]

print(ans)
### BUGGY CODE ###

N = int(input())
l = sorted([int(item) for item in input().split(' ')])
count = 0
 
for i in range(N):
    kmax = N
    for j in range(N-1, i, -1):
        for k in range(j+1, kmax):
            if l[i] + l[j] > l[k]:
                count += 1
            else:
                kmax -= 1
                break
print(count)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(map(int, input().split()))

ans = 0
for i in range(n):
    for j in range(i+1, n):
        end = bisect.bisect_left(l, l[i]+l[j])
        ans += end - j - 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(u, v, pu=-1):
        if u == v: return True
        for cu in to[u]:
            if cu == pu: continue
            if dfs(cu, v, u):
                path.append(uvtoi[u, cu])
                return True
        return False

    to = defaultdict(list)
    n = II()
    uvtoi = {}
    for i in range(n - 1):
        a, b = MI1()
        to[a].append(b)
        to[b].append(a)
        uvtoi[a, b] = i
        uvtoi[b, a] = i
    m = II()
    itoj = defaultdict(list)
    for j in range(m):
        u, v = MI1()
        path = []
        dfs(u, v)
        #print(path)
        for i in path: itoj[i].append(j)
    #print(itoj)
    en = len(itoj)
    dp = [[0] * (1 << m) for _ in range(en + 1)]
    dp[0][0] = 1
    for i, jj in enumerate(itoj.values()):
        mask = sum(1 << j for j in jj)
        for bit in range(1 << m):
            pre = dp[i][bit]
            if pre == 0: continue
            dp[i + 1][bit | mask] += pre
            dp[i + 1][bit] += pre
    #print(dp)
    ans=dp[-1][-1]*pow(2,n-1-en)
    print(ans)

main()


### FIXED CODE ###

from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def dfs(u, v, pu=-1):
        if u == v: return True
        for cu in to[u]:
            if cu == pu: continue
            if dfs(cu, v, u):
                path.append(uvtoi[u, cu])
                return True
        return False

    to = defaultdict(list)
    n = II()
    uvtoi = {}
    for i in range(n - 1):
        a, b = MI1()
        to[a].append(b)
        to[b].append(a)
        uvtoi[a, b] = i
        uvtoi[b, a] = i
    m = II()
    itoj = defaultdict(list)
    for j in range(m):
        u, v = MI1()
        path = []
        dfs(u, v)
        #print(path)
        for i in path: itoj[i].append(j)
    #print(itoj)
    en = len(itoj)
    dp = [[0] * (1 << m) for _ in range(en + 1)]
    dp[0][0] = 1
    for i, jj in enumerate(itoj.values()):
        mask = sum(1 << j for j in jj)
        for bit in range(1 << m):
            pre = dp[i][bit]
            if pre == 0: continue
            dp[i + 1][bit | mask] += pre
            dp[i + 1][bit] += pre
    #print(dp)
    ans=dp[-1][-1]*pow(2,n-1-en)
    print(ans)

main()
### BUGGY CODE ###

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

p=[0]*n
p[0]=1
now=1
cnt=1
k=10**8
while 0 in p and k>0:
    for to in l[now-1]:
        if p[to]==0:
            p[to]=now
    now=to+1
    cnt+=1
    k-=1
if 0 in p:
    print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(p[i])



### FIXED CODE ###

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

from collections import deque

p=[0]*n
ans=[0]*n
d=deque()
d.append(0)
while len(d)!=0:
    now=d.popleft()
    for to in l[now]:
        if p[to]==0:
            p[to]=p[now]+1
            d.append(to)
            ans[to]=now
print("Yes")
for i in range(1,n):
    print(ans[i]+1)
### BUGGY CODE ###

H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

yoko = {}
tate = {}
tate_counter = [0 for i in range(W)]
for h in range(H):
    yoko_counter = 0
    for w in range(W):
        if S[h][w] == '#':
            for i in range(yoko_counter):
                yoko[(h, w - i - 1)] = yoko_counter
            for i in range(tate_counter[w]):
                tate[(h - i - 1, w)] = tate_counter[w]
            yoko_counter = 0
            tate_counter[w] = 0
            continue
        yoko_counter += 1
        tate_counter[w] += 1
    if yoko_counter > 0:
        for i in range(yoko_counter):
            yoko[(h, W - i - 1)] = yoko_counter
for w in range(W):
    if tate_counter[w] > 0:
        for i in range(tate_counter[w]):        
            tate[(H - i - 1, w)] = tate_counter[w]


max_score = 0
for h in range(H):
    for w in range(W):
        if (h,w) in yoko and (h,w) in tate:
            score = yoko[(h,w)] + tate[(h,w)] - 1
            if max_score < score:
                #print(h,w, score)
                max_score = score

print(max_score)

### FIXED CODE ###

H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

left = [[-1 for j in range(W)] for i in range(H)]
right = [[W for j in range(W)] for i in range(H)]
up = [[-1 for j in range(W)] for i in range(H)]
down = [[H for j in range(W)] for i in range(H)]

# from left upper to right down
up_wall = [-1 for i in range(W)]
for h in range(H):
    left_wall = -1    
    for w in range(W):
        if S[h][w] == '#':
            left_wall = w
            up_wall[w] = h
        left[h][w] = left_wall
        up[h][w] = up_wall[w]

# from right down to left up
down_wall = [H for i in range(W)]
for h in range(H - 1, -1, -1):
    right_wall = W
    for w in range(W - 1, -1, -1):
        if S[h][w] == '#':
            right_wall = w
            down_wall[w] = h
        right[h][w] = right_wall
        down[h][w] = down_wall[w]

# print(left)
# print(right)
# print(up)
# print(down)

max_score = 0
for h in range(H):
    for w in range(W):
        left_score = (w - left[h][w])
        right_score = (right[h][w] - w)
        up_score = (h - up[h][w])
        down_score = (down[h][w] - h)
        score = left_score + right_score + up_score + down_score - 3
        # print(h, w, score, left_score, right_score, up_score, down_score)
        if max_score < score:
            max_score = score
print(max_score)
### BUGGY CODE ###

N,K=[int(x) for x in input().rstrip().split()]
p=[int(x) for x in input().rstrip().split()]
ex=[1/2*(i+1) for i in range(1,1001)]

p_x=[0 for i in range(N)]

mx=0
ind=0
for i in range(N-K+1):
  if mx<max(mx,sum(p[i:i+K])):
    ind=i
    mx=max(mx,sum(p[i:i+K]))

# print(ind,mx)
ans=0
for i in range(ind,ind+K):
  ans+=ex[p[i]-1]
print(ans)




### FIXED CODE ###

N,K=[int(x) for x in input().rstrip().split()]
p=[int(x) for x in input().rstrip().split()]
ex=[1/2*(i+1) for i in p]
ruiseki=[0]
ans=0

for i in range(N):
  ruiseki.append(ruiseki[i]+ex[i])


for i in range(N+1-K):
  if ans<ruiseki[i+K]-ruiseki[i]:
    ans=ruiseki[i+K]-ruiseki[i]
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 1
flag = True
for i in range(n):
  ans *= A[i]
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 1
flag = True
if 0 in A:
  print(0)
  flag = False
if flag:
  for i in range(n):
    ans *= A[i]
    if ans > 10**18:
      print(-1)
      flag = False

      break
  if flag:
    print(ans)
### BUGGY CODE ###

import math
A,B,N=map(int,input().split())

a=min(B,N)
array=[]

for x in range(1,a+1):
  array.append(math.floor(A*x/B)-A*math.floor(x/B))
  
print(max(array))
  

### FIXED CODE ###

import math
A,B,N=map(int,input().split())

a=min(B,N)

if a==B:
  print(math.floor(A*(B-1)/B)-A*math.floor((B-1)/B))
else:
  print(math.floor(A*N/B)-A*math.floor(N/B))
### BUGGY CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
ans = 1
for i in a:
    ans *= i
if ans > 10**18:
    ans = -1

print(ans)


### FIXED CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
a.sort()
ans = 1
for i in a:
    if i == 0:
        ans = 0
        break
    ans *= i
    if ans > 10**18:
        ans = -1
        break

print(ans)
### BUGGY CODE ###

n,m = map(int, input().split())
a = list(set([int(input()) for _ in range(m)]))

nums = [0]*(n+1)
nums[0] = 1
if 1 not in a: nums[1] = 1

for i in range(2,n+1):
  if i in a: nums[i] = 0
  else: nums[i] = nums[i-1] + nums[i-2]
print(nums[n]%(10**9+7))

### FIXED CODE ###

n,m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
inf = 1000000007

dp = [0] * (n + 1)
dp[0] = 1
if 1 not in a:
  dp[1] = 1
else:
  dp[1] = 0
  
for i in range(2, n+1):
  if i in a:
    continue
  dp[i] = dp[i - 1] + dp[i - 2]
  dp[i] %= inf
  
print(dp[n])
### BUGGY CODE ###

import heapq
[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
heapq.heapify(A)
ANS = [10**9+1]*N
count = 0
for j in range(N):
    a = heapq.heappop(A)
    for i in range(L):
        try :
            if ANS[a[1]+i] == 10**9+1 :
                ANS[a[1]+i] = a[0]
                count += 1
        except IndexError : continue
    if count == N : break
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 = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

print(*max(A[1:N]))
for i in range(1, N-1):
    print(*max(max(A[0:i]), max(A[i+1:N])))
print(*max(A[0:N-1]))


### FIXED CODE ###

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

max_num = max(A)
max_i = A.index(max_num)
A.remove(max_num)
second_max = max(A)
new_list = [max_num for _ in range(N)]

new_list[max_i] = second_max
print(*[val for sublist in new_list for val in sublist], sep='\n')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    xy=[tuple(map(int,input().split())) for _ in range(n)]
    ans=INF
    from itertools import product
    for a,b,c,d in product(xy,repeat=4):
        x0=a[0]
        x1=b[0]
        y0=c[1]
        y1=d[1]
        count=0
        for x,y in xy: count+=(x0<=x<=x1 and y0<=y<=y1)
        if count>=k: ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    X=[0]*n
    Y=[0]*n
    for i in range(n):
        X[i],Y[i]=map(int,input().split())
    ans=INF
    for a in range(n):
        for b in range(n):
            for c in range(a+1,n):
                for d in range(b+1):
                    x0,x1=sorted([X[a],X[c]])
                    y0,y1=sorted([Y[b],Y[d]])
                    count=0
                    for i in range(n):
                        if x0<=X[i]<=x1 and y0<=Y[i]<=y1:
                            count+=1
                    if count>=k:
                        ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()
### BUGGY CODE ###

import sys

input=sys.stdin.readline
s=input()
t=input()
n,m=len(s),len(t)

dp=[['']*(m+1) for i in range(n+1)]

for i in range(n):
  for j in range(m):
    if s[i]!=t[j]:
      x=len(dp[i+1][j])
      y=len(dp[i][j+1])
      if x>y:
        dp[i+1][j+1]=dp[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
    else:
      x=len(dp[i][j])+1
      y=len(dp[i+1][j])
      z=len(dp[i][j+1])
      tmp=max(x,y,z)
      if x==tmp:
        dp[i+1][j+1]=dp[i][j]+s[i]
      elif  y==tmp:
        dp[i+1][j+1]=dp[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
print(dp[n][m])
      

### FIXED CODE ###

import sys

input=sys.stdin.readline
s=input()
t=input()
n,m=len(s),len(t)

dp=[[0]*(m+1) for i in range(n+1)]
ans=[]

for i in range(n):
  for j in range(m):
    if s[i]!=t[j]:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
    else:
      dp[i+1][j+1]=dp[i][j]+1
      
i,j=n,m      
while i>0 and j>0:
  if s[i-1]==t[j-1]:
    ans.append(s[i-1])
    i-=1
    j-=1
  elif dp[i][j]==dp[i-1][j]:
    i-=1
  else:
    j-=1
print(''.join(ans[::-1]))
### BUGGY CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    sum_val = 0
    num = 10 ** 9 + 7
    for i in range(0, n - 1):
        sum_val += a[i] * sum(a[i+1:])
        if sum_val > num:
            sum_val %= num
    print(sum_val)



### FIXED CODE ###

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    cumsum_a = [0] * len(a)
    cumsum_a[0] = a[0]
    for i in range(1, len(a)):
        cumsum_a[i] += cumsum_a[i-1] + a[i]

    sum_val = 0
    num = 10 ** 9 + 7
    for i in range(0, n - 1):
        sum_val += a[i] * (cumsum_a[-1] - cumsum_a[i])
        if sum_val > num:
            sum_val %= num
    print(sum_val)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n])
INF = 10 ** 18
ans = [INF] * n

q = [(0, ss, 0, 0)]  # (time, silver, city, type)
visited = set()
fixed = 0
while q:
    t, s, v, z = heappop(q)
    if (s, v) in visited:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        if (ns, u) in visited:
            continue
        heappush(q, (t + b, ns, u, 0))

    if z == 1:
        continue

    ts = s
    tt = t
    c, d = exchanges[v]
    while ts <= req:
        ts += c
        tt += d
        if (ts, v) in visited:
            break
        heappush(q, (tt, ts, v, 1))

print('\n'.join(map(str, ans[1:])))


### FIXED CODE ###

import sys
from heapq import heappop, heappush

n, m, ss = map(int, input().split())
lines = sys.stdin.readlines()
links = [set() for _ in range(n)]
aaa = []
for line in lines[:m]:
    u, v, a, b = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, a, b))
    links[v].add((u, a, b))
    aaa.append(a)

exchanges = []
for line in lines[m:]:
    c, d = map(int, line.split())
    exchanges.append((c, d))

req = sum(sorted(aaa, reverse=True)[:n - 1])
INF = 10 ** 18
ans = [INF] * n
ans_silver = [-1] * n

q = [(0, ss, 0)]  # (time, silver, city)
visited = set()
fixed = 0
while q:
    t, s, v = heappop(q)
    if (s, v) in visited or ans_silver[v] >= s:
        continue
    visited.add((s, v))
    if ans[v] == INF:
        ans[v] = t
        ans_silver[v] = s
        fixed += 1
        if fixed == n:
            break

    for u, a, b in links[v]:
        if s < a:
            continue
        ns = s - a
        nt = t + b
        if (ns, u) in visited or ans_silver[u] >= ns:
            continue
        heappush(q, (nt, ns, u))

    c, d = exchanges[v]
    ns = s + c
    if ns <= req and (ns, v) not in visited:
        heappush(q, (t + d, ns, v))

print('\n'.join(map(str, ans[1:])))
### BUGGY CODE ###

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

count =[0 for i in range(N)]
for i in range(N):
    count[A_n[i]-1] +=1
ans =[count[i]*(count[i]-1)//2 for i in range(N)]

for i in range(N):
    print(sum(ans)-count[A_n[i]-1]+1)

### FIXED CODE ###

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

count =[0 for i in range(N)]
for i in range(N):
    count[A_n[i]-1] +=1
ans =[count[i]*(count[i]-1)//2 for i in range(N)]
a1=sum(ans)
for i in range(N):
    print(a1-count[A_n[i]-1]+1)
### BUGGY CODE ###

from itertools import product as pd
f=lambda x,y:(x,y) if x<y else (y,x) 
n,k=map(int,input().split())
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,b,c,d) in pd(range(n),repeat=4):
  lx,rx=f(o[a][0],o[b][0])
  dy,uy=f(o[c][1],o[d][1])
  if lx==rx or dy==uy:continue
  cnt=sum(1 for i in range(n) if lx<=o[i][0]<=rx and dy<=o[i][1]<=uy)
  if cnt==k:
    v=min(v,(rx-lx)*(uy-dy))
print(v)

### FIXED CODE ###

from itertools import combinations as comb
n,k=map(int,input().split())
f=lambda x,y:(min(x,y),max(x,y))
o=[tuple(map(int,input().split())) for _ in range(n)]

v=float("inf")
for (a,b) in comb(range(n),2):
  for (c,d) in comb(range(n),2):
    lx,rx=f(o[a][0],o[b][0])
    dy,uy=f(o[c][1],o[d][1])
    cnt=0
    for i in o:
      if lx<=i[0]<=rx and dy<=i[1]<=uy:
        cnt+=1
    if cnt>=k:
      v=min(v,(rx-lx)*(uy-dy))
print(v)
### BUGGY CODE ###

from fractions import Fraction
n=int(input())
N=Fraction(4,n)
for i in range(1,3501):
    for j in range(1,3501):
        if (N-Fraction(1,i)-Fraction(1,j)).numerator==1:
            print(i,j,(N-Fraction(1,i)-Fraction(1,j)).denominator)
            exit()

### FIXED CODE ###

n=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        if 4*i*j-n*i-n*j>0 and i*j*n%(4*i*j-n*i-n*j)==0:
            print(i,j,i*j*n//(4*i*j-n*i-n*j))
            exit()
### BUGGY CODE ###

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

def f(i,j):
  if j <= X:
    return j-i
  elif Y <= i:
    return j-i
  elif X <= i and j <= Y:
    return min(j-i,(i-X)+1+(Y-j))
  elif i <= X and Y <= j:
    return (X-i)+1+(j-Y)
  elif i <= X and X <= j and j <= Y:
    return (X-i)+min(j-X,1+(Y-j))
  else:
    return (j-Y)+min(Y-i,(i-X)+1)

A = []

for k in range(1,N,1):
  for l in range(k+1,N+1,1):
    A.append(f(k,l))

for k in range(1,N,1):
  print(A.count(k))

### FIXED CODE ###

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

def f(i,j):
  if j <= X:
    return j-i
  elif Y <= i:
    return j-i
  elif X <= i and j <= Y:
    return min(j-i,(i-X)+1+(Y-j))
  elif i <= X and Y <= j:
    return (X-i)+1+(j-Y)
  elif i <= X and X <= j and j <= Y:
    return (X-i)+min(j-X,1+(Y-j))
  else:
    return (j-Y)+min(Y-i,(i-X)+1)

A = [0]*(N-1)

for k in range(1,N,1):
  for l in range(k+1,N+1,1):
    A[f(k,l)-1] += 1

for k in range(1,N,1):
  print(A[k-1])
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A = [input() for _ in range(H)]

que = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            que.append((h, w, 0))

minDist = [[10**10] * W for _ in range(H)]
while que:
    h, w, d = que.popleft()

    if minDist[h][w] <= d:
        continue
    minDist[h][w] = d

    for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        if 0 <= dh + h < H and 0 <= dw + w < W:
            que.append((dh + h, dw + w, d + 1))

ans = max(max(d) for d in minDist)
print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
A = [input() for _ in range(H)]

minDist = [[10**10] * W for _ in range(H)]
que = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            que.append((h, w, 0))
            minDist[h][w] = 0

while que:
    h, w, d = que.popleft()

    if minDist[h][w] < d:
        continue
    minDist[h][w] = d

    for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        if 0 <= dh + h < H and 0 <= dw + w < W:
            if minDist[dh + h][dw + w] > d + 1:
                que.append((dh + h, dw + w, d + 1))
                minDist[dh + h][dw + w] = d + 1

ans = max(max(d) for d in minDist)
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
result = 1
flag = 0
for a in A:
    if a == 0:
        result = 0
        break
    else:
        result = result * a
        if result > pow(10, 18):
            flag = 1
            result = -1
if flag == 1 and result != 0:
    print(-1)
else:
    print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
result = 1
flag = 0
zero_flag = 0
for a in A:
    if a == 0:
        zero_flag = 1
        result = 0
        break
    else:
        result = result * a
        if result > pow(10, 18):
            flag = 1
            result = 0
if flag == 1 and zero_flag != 1:
    print(-1)
else:
    print(result)
### BUGGY CODE ###

def main():
    N,K = map(int,input().split())
    A = [int(input()) for _ in range(N)]
    dp2 = [0] * N
    max0 = 0
    for i in range(N):
        tmax = 0
        for j in range(i+1):
            if -K <= (A[i]-A[j]) <= K:
                tmax = max(tmax,dp2[j]+1)
        dp2[i] = tmax  
        max0 = max(max0,tmax)
    print(max0)
main()

### FIXED CODE ###

# Input Part
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]

Amax = 3*10**5

# N: 処理する区間の長さ
N0 = 2**(Amax-1).bit_length()
INF = 0
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

def main():
    for i in range(N):
        tmin = max(0,A[i]-K)
        tmax = min(Amax,A[i]+K)+1
        update(A[i],query(tmin,tmax)+1)
        #print(data)
    print(data[0])
main()