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

import sys
sys.setrecursionlimit(10**5)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False

def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if (x,y) not in finished:
            finished.add((x,y))
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    dfs(i)
    ans += black * white
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if x+y*w not in finished:
            finished.add(x+y*w)
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        if (x+i)+(y+j)*w not in finished:
                            que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
"""
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
"""
for y in range(h):
    for x in range(w):
        for i in range(-1,2,1):
            for j in range(-1,2,1):
                if abs(i) + abs(j) < 2 and check(y+j,x+i):
                    if grid[y][x] != grid[y+j][x+i]:
                        adjacent_list[x+w*y].append((x + i)+w*(y + j))
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)
### BUGGY CODE ###

N,M,K = map(int,input().split())
a = list(map(int,input().split()))	
b = list(map(int,input().split()))
A = [0]
B = [0]
A.extend(a)
B.extend(b)
time = sum(A)
ai = len(A)-1
bi = 0
con = 0
flg = None
count = 0
if len(a) == 1 or len(b)==1:
    time = 0
    while True:
        if len(a) == 0 and len(b)==0:
            break
        elif len(a) == 0:
            time += b[0]
            b.pop(0)
        elif len(b) == 0:
            time += a[0]
            a.pop(0)
        elif a[0] > b[0]:
            time += b[0]
            b.pop(0)
        else:
            time += a[0]
            a.pop(0)   
        if time >K:
            break
        count += 1
    print(count)
else:
    while True:
        #print("---------")
        #print(str(ai)+":"+str(bi))
        if time > K:
            if flg is not None:
                con = max(con,flg-1)
                flg = None
            
            if ai == 0:
                break
            time -=A[ai]
            ai -= 1
        else:
            #print("b")
            flg = ai+bi
            time +=B[bi]
            bi += 1
            if bi == len(B):
                if time > K:
                    pass
                else:
                    con = max(con,ai+bi-1)
                break
        #print(flg)
    print(con)

### FIXED CODE ###

N,M,K = map(int,input().split())
a = list(map(int,input().split()))	
b = list(map(int,input().split()))

A = [0]
B = [0]
A.extend(a)
B.extend(b)
time = sum(A)
ai = len(A)-1
bi = 0
con = 0
flg = None
count = 0

    

while True:
    #print("---------")
    #print(str(ai)+":"+str(bi))
    if time > K:
        if flg is not None:
            con = max(con,flg-1)
            flg = None
        
        if ai == 0:
            break
        time -=A[ai]
        ai -= 1
    else:
        #print("b")
        flg = ai+bi
        time +=B[bi]
        bi += 1
        if bi == len(B):
            if time > K:
                if flg is not None:
                    con = max(con, flg-1)
                pass
            else:
                con = max(con,ai+bi-1)
            break
    #print(flg)
print(con)
### BUGGY CODE ###

n,s=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
ans=0
dp=[[[0 for _ in range(s+1)] for _ in range(n+1)] for _ in range(n+1)]
for i in range(n+1):
    dp[i][0][0]=1

for i in range(n):
    for k in range(1,i+2):
        for c in range(1,s+1):
            if c>=A[i]:
                dp[i+1][k][c]=dp[i][k][c]+dp[i][k-1][c-A[i]]
            else:
                dp[i+1][k][c]=dp[i][k][c]

for i in range(1,n+1):
    ans+=dp[n][i][s]*pow(2,n-i,mod)
print(ans%mod)

### FIXED CODE ###

n,s=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
ans=0
dp=[[0 for _ in range(s+1)] for _ in range(n+1)]
dp[0][0]=1

for i in range(n):
    for c in range(s+1):
        if c>=A[i]:
            dp[i+1][c]=(2*dp[i][c]+dp[i][c-A[i]])%mod
        else:
            dp[i+1][c]=(2*dp[i][c])%mod

print(dp[n][s]%mod)
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    divisor=0
    for j in range(1,n+1):
        if i%j==0:
            divisor+=1
    ans+=(divisor*i)      
print(ans)    

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    x=n//i
    ans+=(x*(x+1)//2)*i
print(ans)
### BUGGY CODE ###

def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

n = iip()
al = iip()

mod = 10**9 + 7
num1 = [0 for i in range(60)]

for a in al:
    b = bin(a)[2:].zfill(60)
    #print(b)
    for i in range(60):
        if b[i] == "1":
            num1[i] += 1

result = 0
for i, a in enumerate(num1):
    a1 = 2**(59-i) % mod
    a2 = (a * (n-a)) % mod
    result += a1*a2 % mod
    result = result % mod


#print(num1)
print(result)

### FIXED CODE ###

def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

n = iip()
al = iip()
#al = [2**60 - 114514 - i for i in range(1000)]

mod = 10**9 + 7
num1 = [0 for i in range(60)]

for a in al:
    b = bin(a)[2:].zfill(60)
    #print(b)
    for i in range(60):
        if b[i] == "1":
            num1[i] += 1

result = 0
for i, a in enumerate(num1):
    a1 = 2**(59-i) % mod
    a2 = (a * (n-a)) % mod
    result += a1*a2 % mod
    result = result % mod


#print(num1)
print(result)
### BUGGY CODE ###


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

from math import gcd


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

g = 0
for aa in a:
    g = gcd(g,aa)
if g > 1:
    print('not coprime')
    exit()

def eratosthenes(limit):
    import math
    if not isinstance(limit, int):
        raise TypeError('n is int type.')
    if limit < 2:
        raise ValueError('n is more than 2')
    prime = []
    sqrt_limit = math.sqrt(limit)
    prime_numbers_list = [i + 1 for i in range(1, limit)]
    while True:
        p = prime_numbers_list[0]
        if sqrt_limit <= p:
            return prime + prime_numbers_list
        prime.append(p)
        prime_numbers_list = [e for e in prime_numbers_list if e % p != 0]
    return prime_numbers_list


if a[-1]==1:
    print('pairwise coprime')
    exit()

prime_numbers_list = eratosthenes(n)

count = [0]*len(prime_numbers_list)

for aa in a:
    for i, prime in enumerate(prime_numbers_list):
        if aa % prime ==0:
            count[i] += 1
            if count[i]==2:
                print('setwise coprime')
                exit()
            break

print('pairwise coprime')




### FIXED CODE ###

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

from math import gcd
n = int(input())
a = list( map(int, input().split()))


g = 0
for aa in a:
    g = gcd(g,aa)
if g > 1:
    print('not coprime')
    exit()

MAXN = 10**6+10

def eratosthenes3(limit):
    sieve = [i for i in range(limit+1)]
    p = 2
    while p*p <= limit:
        if sieve[p] == p:
            for q in range(2*p,limit+1,p):
                if sieve[q] == q:
                    sieve[q] = p
        p += 1

    return sieve

sieve = eratosthenes3(MAXN)

st = set()
for aa in a:
    tmp = set()
    while aa > 1:
        tmp.add(sieve[aa])
        aa //= sieve[aa]
    for p in tmp:
        if p in st:
            print('setwise coprime')
            exit()
        st.add(p)
print('pairwise coprime')
### BUGGY CODE ###

# 2019-11-14 10:01:24(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    H, W = [int(x) for x in sys.stdin.readline().split()]
    grid = ['#' * (W + 2)]
    for _ in range(H):
        # s = f'#{sys.stdin.readline().rstrip()}#'
        s = '#' + sys.stdin.readline().rstrip() + '#'
        grid.append(s)
    grid.append('#' * (W + 2))

    lighted_squares = []
    for h in range(1, H+1):
        for w in range(1, W+1):
            if grid[h][w] == '#':
                lighted_squares.append(0)
            else:
                count = 1
                for j in range(w-1, -1, -1):
                    if grid[h][j] == '.':
                        count += 1
                        continue
                    else:
                        break
                for j in range(w+1, W+2):
                    if grid[h][j] == '.':
                        count += 1
                        continue
                    else:
                        break
                for i in range(h-1, -1, -1):
                    if grid[i][w] == '.':
                        count += 1
                        continue
                    else:
                        break
                for i in range(h+1, H+2):
                    if grid[i][w] == '.':
                        count += 1
                        continue
                    else:
                        break
                lighted_squares.append(count)
    
    print(max(lighted_squares))




if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import numpy as np 

h, w = map(int, sys.stdin.readline().split())
grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(h)], dtype='U')
grid = np.pad(grid, 1, mode='constant')

def main():
    cnt = np.zeros((h+2, w+2))
    cnt[grid == '.'] = np.inf
    
    l = cnt.copy()
    r = cnt.copy()
    u = cnt.copy()
    d = cnt.copy()

    for i in range(1, w+1):
        l[1:h+1, i] = np.minimum(l[1:h+1, i], l[1:h+1, i-1]+1)
        i = w + 1 - i
        r[1:h+1, i] = np.minimum(r[1:h+1, i], r[1:h+1, i+1]+1)
    
    for i in range(1, h+1):
        u[i, 1:w+1] = np.minimum(u[i, 1:w+1], u[i-1, 1:w+1]+1)
        i = h + 1 - i
        d[i, 1:w+1] = np.minimum(d[i, 1:w+1], d[i+1, 1:w+1]+1)
    
    res = np.maximum(l + r + u + d - 3, 0).astype(np.int64)
    return np.amax(res)

if __name__ == '__main__':
    ans = main()
    print(ans)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
ans = [K]*N
for i in range(1, Q+1): # round
    for j in range(1, N+1):
        if A[i-1] != j:
            ans[j-1] -= 1
for k in ans:
    if k <= 0:
        print('No')
    else:
         print('Yes')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
ans = [K-Q]*N
for i in range(1,Q+1):
    ans[A[i-1]-1] += 1    
for k in ans:
    if k <= 0:
        print('No')
    else:
         print('Yes')
### BUGGY CODE ###

from collections import defaultdict
N,S = open(0).read().split()
N = int(N)
ldic = defaultdict(int)
rdic = defaultdict(int)
L = S[:N]
R = S[N:][::-1]
for i in range(2**N):
  la = ''
  lb = ''
  ra = ''
  rb = ''
  for j in range(N):
    if i%2==1:
      la += L[j]
      ra += R[j]
    else:
      lb += L[j]
      rb += R[j]
    i >>= 1
  ldic[(la,lb)] += 1
  rdic[(ra,rb)] += 1
ans = sum(rdic[k]*ldic[k] for k in ldic.keys())
print(ans)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
S = input()
S = S[:N]+S[2*N-1:N-1:-1]
ldic = defaultdict(int)
rdic = defaultdict(int)
for i in range(2**N):
  lred = ""
  lblue = ""
  rred = ""
  rblue = ""
  for j in range(N):
    if i%2==1:
      lred += S[j]
      rred += S[N+j]
    else:
      lblue += S[j]
      rblue += S[N+j]
    i >>= 1
  ldic[(lred,lblue)] += 1
  rdic[(rred,rblue)] += 1

ans = 0
for k in ldic.keys():
  ans += ldic[k]*rdic[k]
print(ans)
### BUGGY CODE ###

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

from copy import deepcopy
import itertools

h,w=n1()
s=s2(h)
s=["#"+x+"#" for x in s]
s=["#"*(w+2)]+s+["#"*(w+2)]
meiro_original=[[0]*(w+2) for _ in range(h+2)]
road=[]
for i in range(len(s)):
    for j in range(len(s[i])):
        if s[i][j]=="#":
            meiro_original[i][j]=2
        else:
            meiro_original[i][j]=0
            road.append([i,j])

def calc(start):
    ans=0
    meiro=deepcopy(meiro_original)
    pos=[[start[0],start[1],0]]
    while len(pos)>0:
        x,y,c=pos.pop(0)

        meiro[x][y]=2

        f=False
        if meiro[x-1][y]<2:
            pos.append([x-1,y,c+1])
            f=True
        if meiro[x+1][y]<2:
            pos.append([x+1,y,c+1])
            f=True
        if meiro[x][y-1]<2:
            pos.append([x,y-1,c+1]) 
            f=True
        if meiro[x][y+1]<2:
            pos.append([x,y+1,c+1])
            f=True
        if f==False:
            ans=max(ans,c)   
    return ans

l=0
for x in road:
    l=max(l,calc(x))
    
print(l)  

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop

h,w=n1()
s=s4(h)
def make_around(s,h):
    sss=[[-1]*(w+2)]
    for line in s:
        sss.append([-1]+[-1 if i=="#" else 0 for i in line ]+[-1])
    sss.append([-1]*(w+2))
    return sss

s=make_around(s,h)
d=[]
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]==0:
            d.append((i,j))

from copy import deepcopy
ans=0
for i in range(len(d)):
    ss=deepcopy(s)
    x,y=d[i]
    q=deque([(x,y)])
    ss[x][y]=1
    while len(q)>0:
        x,y=q.popleft()
        if ss[x+1][y]==0:
            ss[x+1][y]=ss[x][y]+1
            q.append((x+1,y))
        if ss[x-1][y]==0:
            ss[x-1][y]=ss[x][y]+1
            q.append((x-1,y))
        if ss[x][y+1]==0:
            ss[x][y+1]=ss[x][y]+1
            q.append((x,y+1))
        if ss[x][y-1]==0:
            ss[x][y-1]=ss[x][y]+1
            q.append((x,y-1))
    ans=max(ans,max(list(itertools.chain.from_iterable(ss))))
print(ans-1)
### BUGGY CODE ###

#関数リスト
import sys
from bisect import bisect
input = sys.stdin.readline
def RD(): return input().rstrip()
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N = I()
    A = LI()
    A.sort()
    B = LI()
    B.sort()
    B_len = len(B)
    C = LI()
    C.sort()
    C_len = len(C)
    result = 0
    A_init = A[0]
    index = 0
    next_i = index
    
    for i in A:
        index = next_i
        for j in range(index, B_len):
            if B[j] <= i:
                next_i = j+1
            else:
                result += C_len - bisect(C,B[j])
    print(result)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#関数リスト
import sys
import bisect
input = sys.stdin.readline
def RD(): return input().rstrip()
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def main():
    N = I()
    A = LI()
    A.sort()
    B = LI()
    B.sort()
    B_len = len(B)
    C = LI()
    C.sort()
    C_len = len(C)
    result = 0
    A_init = A[0]
    index = 0
    next_i = index
    
    for i in B:
        tempA = bisect.bisect_left(A,i) 
        tempC = C_len - bisect.bisect_right(C,i)
        result += tempA*tempC
    print(result)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

ans = [0] * N
bit = 0
for i in range(1, N):
    ans[i] = a[i - 1] ^ a[i] ^ ans[i - 1]
    bit ^= ans[i]

if bit == a[0]:
    print(' '.join(map(str, ans)))
else:
    index = 0
    for i in range(1, 10 ** 9 + 1):
        bit = bit ^ (i - 1) ^ i
        if bit == a[0]:
            index = i
            break

    ans[0] = index
    for i in range(1, N):
        ans[i] = a[i - 1] ^ a[i] ^ ans[i - 1]
        bit ^= ans[i]

    print(' '.join(map(str, ans)))


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
S = 0
for i in range(N):
    S ^= a[i]

ans = [0] * N

for i in range(N):
    ans[i] = S ^ a[i]

print(' '.join(map(str, ans)))
### BUGGY CODE ###

n, k, q = map(int, input().split())
points = [k] * n


for _ in range(q):
    win = int(input())
    points = [p-1 for p in points]
    points[win-1] += 1

for i in points:
    if i >= 1:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
points = [k] * n


for _ in range(q):
    win = int(input())
    points[win-1] += 1

points = [p-q for p in points]
for i in points:
    if i >= 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
result = 0

for i in range(n):
    for j in range(i, n):
        if sum(a[i:j+1]) == 0:
            result += 1

print(result)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = [0]
for i in range(n):
    s.append(s[-1] + a[i])
s.sort()
result = 0

count = 1
for i in range(n):
    if s[i] == s[i+1]:
        count += 1
    else:
        result += count * (count - 1) // 2
        count = 1
result += count * (count - 1) // 2

print(result)
### BUGGY CODE ###

from queue import Queue
h,w = map(int, input().split(' '))
s = [list(input()) for _ in range(h)]
num_w = 0
for i in range(h):
    num_w += s[i].count("#")
q = Queue()
cnt = 0
q.put((0,0,0))
Z = -1
while not q.empty():
    (x,y,cnt) = q.get()
    s[x][y] = "#"
    if (x,y) == (h-1,w-1):
        Z = cnt
        break
    if x!=h-1 and s[x+1][y]!="#":
        q.put((x+1,y,cnt+1))
    if x!=0 and s[x-1][y]!="#":
        q.put((x-1,y,cnt+1))
    if y!=w-1 and s[x][y+1]!="#":
        q.put((x,y+1,cnt+1))
    if y!=0 and s[x][y-1]!="#":
        q.put((x,y-1,cnt+1))
if Z == -1:
    print(-1)
else:
    print(h*w-Z-1-num_w)


### FIXED CODE ###

from queue import Queue
h,w = map(int, input().split(' '))
s = [list(input()) for _ in range(h)]
num_w = 0
for i in range(h):
    num_w += s[i].count("#")
for i in range(h):
    s[i] = ["#"]+s[i]+["#"]
s.insert(0,["#" for i in range(w+2)])
s.append(["#" for i in range(w+2)])
q = Queue()
cnt = 0
q.put([1,1,0])
s[1][1]="#"
Z = -1
while (not q.empty()):
    x,y,cnt = q.get()
    if (x,y) == (h,w):
        Z = cnt
        break
    for (i,j) in [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]:
        if s[i][j] != "#":
            s[i][j] = "#"
            q.put([i,j,cnt+1])
if Z == -1:
    print(-1)
else:
    print(h*w-Z-1-num_w)
### BUGGY CODE ###

n,q = map(int,input().split())
S = input()
d = [0] * n
for i in range(n - 1):
        if S[i]+S[i + 1] == 'AC':
                d[i+1] += 1
for i in range(q):
        r,l = map(int,input().split())
        su = 0
        for j in range(r-1,l):
                su += d[j]
        print(su-d[r-1])

### FIXED CODE ###

n,q = map(int,input().split())
S = input()
d = [0] * n
counter = 1
for i in range(n - 1):
    d[i] = counter
    if S[i]+S[i + 1] == 'AC':
            d[i+1] = counter
            counter += 1
d[len(S)-1] = counter
for i in range(q):
    r,l = map(int,input().split())
    print(d[l-1]-d[r-1])
### BUGGY CODE ###

N=int(input())
S=input()
count=0
R=0
G=0
B=0
for i in range(N):
  if S[i]=="R":
    R+=1
  if S[i]=="G":
    G+=1
  if S[i]=="B":
    B+=1
count=0
for i in range(N-2):
  for j in range(i,N-1):
    k=j+j-i
    try:
      if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
        count+=1
    except:
      pass
    
print(R*G*B-count)

### FIXED CODE ###

N=int(input())
S=input()
count=0
R=0
G=0
B=0
for i in range(N):
  if S[i]=="R":
    R+=1
  if S[i]=="G":
    G+=1
  if S[i]=="B":
    B+=1
count=0
for i in range(N-2):
  for j in range(i,N-1):
    k=j+j-i
    try:
      if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
        count+=1
    except:
      pass
    
print(R*G*B-count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def main():
  def s(l,r):
    if(l,r)in d:return d[(l,r)]
    if r-l<2:return 0
    d[(l,r)]=min(s(l,i)+s(i,r)for i in range(l+1,r))+a[r-1]-a[l-1]
    return d[(l,r)]
  d={}
  n,*a=map(int,open(0).read().split())
  for i in range(n-1):a[i+1]+=a[i]
  a+=[0]
  print(s(0,n))
main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def main():
  def s(l,r):
    k=l*n+r
    if d[k]:return d[k]
    if r-l<2:return 0
    d[k]=t=min(s(l,i)+s(i,r)for i in range(l+1,r))+a[r-1]-a[l-1]
    return t
  n,*a=map(int,open(0).read().split())
  d=[None]*(n*n+1)
  for i in range(n-1):a[i+1]+=a[i]
  a+=[0]
  print(s(0,n))
main()
### BUGGY CODE ###

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

# dpテーブル
dp = [10 ** 9] * N

# 初期値
dp[0] = 0
dp[1] = abs(h[1] - h[0])

# ループ
for i in range(2, N):
    dp[i] = min((dp[i - j] + abs(h[i] - h[i - j])) for j in range(min(i + 1, K + 1)))
        
# 解を出力
print(dp[N - 1])


### FIXED CODE ###

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

# DPテーブル
dp = [10 ** 10] * N

# 初期値
dp[0] = 0

# ループ
for i in range(1, N):
    for j in range(1, K + 1):
        if i - j < 0:
            pass
        else:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

# 解を出力
print(dp[N - 1])