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

N = int(input())
dis = [0]*N
G = [[] for _ in range(N)]
for _ in range(N-1):
	u, v, w = map(int, input().split())
	u -= 1
	v -= 1
	G[u].append((v, w))
	G[v].append((u, w))

queue = [0]
V = [0]*N
idx = 1

while queue:
	u = queue.pop()
	for i in G[u]:
		v, w = i
		if v not in V:
			V[idx] = v
			idx += 1
			queue.append(v)
			dis[v] = dis[u] + w
		if idx == N:
			break
	if idx == N:
		break

for i in dis:
	print(1 if i % 2 else 0)

### FIXED CODE ###

N = int(input())
INF = float('inf')
dis = [INF]*N
dis[0] = 0
G = [[] for _ in range(N)]
for _ in range(N-1):
	u, v, w = map(int, input().split())
	u -= 1
	v -= 1
	G[u].append((v, w))
	G[v].append((u, w))

queue = [0]

while queue:
	u = queue.pop()
	for v, w in G[u]:
		if dis[v] > dis[u] + w:
			queue.append(v)
			dis[v] = dis[u] + w

for i in dis:
	print(i % 2)
### BUGGY CODE ###

from collections import deque

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
ans = [[-1]*W for _ in range(H)]
q = deque()

for i in range(H):
    for j in range(W):
        if l[i][j] == '#':
            q.append([i,j])
            ans[i][j] = 0

t = 0
while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if ans[next_i][next_j] == -1 and l[next_i][next_j] == '.':
                ans[next_i][next_j] = ans[i][j] + 1
                t = max(t, ans[next_i][next_j])
                q.append([next_i,next_j])

print(t)


### FIXED CODE ###

from collections import deque

H,W = [int(i) for i in input().split()]
l = [list(input()) for _ in range(H)]
ans = [[-1]*W for _ in range(H)]
q = deque()

for i in range(H):
    for j in range(W):
        if l[i][j] == '#':
            q.append([i,j])
            ans[i][j] = 0

t = 0
while q:
    i,j = q.popleft()
    for next_i, next_j in [[i+1,j], [i-1,j], [i,j+1], [i,j-1]]:
        if 0 <= next_i < H and 0 <= next_j < W:
            if ans[next_i][next_j] == -1 and l[next_i][next_j] == '.':
                ans[next_i][next_j] = ans[i][j] + 1
                t = max(t, ans[next_i][next_j])
                q.append([next_i,next_j])

print(t)
### BUGGY CODE ###

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 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]

class Segtree():
    def __init__(self, aa):
        self.inf = 0
        self.n = n = len(aa)
        self.tree_width = tree_width = 1 << (n - 1).bit_length()
        self.tree = [-self.inf] * (tree_width * 2 - 1)
        self.tree[tree_width-1:tree_width-1+n]=aa
        for u in range(tree_width - 2, -1, -1):
            self.tree[u] = self.tree[u * 2 + 1]+self.tree[u * 2 + 2]

    def add(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] += a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = self.tree[seg_i * 2 + 1]+self.tree[seg_i * 2 + 2]

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最大値
    def sum(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return 0
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.sum(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.sum(l, r, seg_i * 2 + 2, segM, segR)
        return ret0+ret1

n,q=MI()
cc=LI()
lri=[]
mx=500005
#mx=10
for i in range(q):
    l,r=MI()
    l-=1
    lri.append((l,r,i))

lri.sort(key=lambda x:x[1])

#print(lri)
last=[-1]*mx
st=Segtree([0]*mx)
ans=[0]*q
now=0
for l,r,i in lri:
    for j in range(now,r):
        c=cc[j]
        pre=last[c]
        if pre!=-1:st.add(pre,-1)
        last[c]=j
        st.add(j,1)
    #print(l,r,st.tree,last)
    now=r
    ans[i]=st.sum(l,r)
print(*ans,sep="\n")



### FIXED CODE ###

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 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]

class BitSum:
    def __init__(self, n):
        self.n = n + 1
        self.table = [0] * self.n

    def add(self, i, x):
        i += 1
        while i < self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

n,q=MI()
cc=LI()
lri=[]
mx=500005
#mx=10
for i in range(q):
    l,r=MI()
    l-=1
    lri.append((l,r-1,i))

lri.sort(key=lambda x:x[1])

#print(lri)
last=[-1]*mx
st=BitSum(mx)
ans=[0]*q
now=0
for l,r,i in lri:
    for j in range(now,r+1):
        c=cc[j]
        pre=last[c]
        if pre!=-1:st.add(pre,-1)
        last[c]=j
        st.add(j,1)
    #print(l,r,st.tree,last)
    now=r+1
    ans[i]=st.sum(r)-st.sum(l-1)
print(*ans,sep="\n")
### BUGGY CODE ###

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

def cn(A,B):
    ans = 0
    pre = B
    score = A*B
    for i in range(A+1,score+1):
        tmp = (score-1)//i
        if tmp < 1:
            break
        if tmp == pre:
            ans += pre-1
            break
        ans += 1
        pre = tmp
    return ans
for ab in AB:
    print(cn(ab[0],ab[1])+cn(ab[1],ab[0]))


### FIXED CODE ###

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

def cn(A,B):
    score = A*B-1
    L = A+1
    R = score
    if L>R:
        return 0
    while L!=R:
        tmp = (L+R)//2
        if score > tmp*(tmp+1):
            L = tmp+1
        else:
            R = tmp
    return (L-1-A+score//L)
for ab in AB:
    print(cn(ab[0],ab[1])+cn(ab[1],ab[0]))
### BUGGY CODE ###

# E
from collections import Counter

H,W,M=map(int,input().split())
h,w,bomb=[0]*M,[0]*M,[]
for i in range(M):
    h[i],w[i]=map(int,input().split())
    bomb.append((h[i],w[i]))

most_h,most_w=Counter(h).most_common(),Counter(w).most_common()

def max_values(lis):
    max_num=lis[0][1]
    for i in range(len(lis)):
        if lis[i][1]<max_num:
            res=lis[:i]
            break
    else:
        res=lis
    return res

most_h=max_values(most_h)
most_w=max_values(most_w)

res=-1
for i,i_n in most_h:
    for j,j_n in most_w:
        if not (i,j) in bomb:
            res=i_n+j_n
            break
    if res>-1:
        break
else:
    res=i_n+j_n-1
print(res)


### FIXED CODE ###

H,W,M=map(int,input().split())
h,w,bomb=[0]*H,[0]*W,[]
for i in range(M):
    a,b=map(int,input().split())
    bomb.append((a-1,b-1))
    h[a-1]+=1
    w[b-1]+=1
    
max_h=max(h)
max_w=max(w)

bomb_and_max=0
for i,j in bomb:
    if h[i]==max_h and w[j]==max_w:
        bomb_and_max+=1
    
if bomb_and_max==h.count(max_h)*w.count(max_w):
    print(max_h+max_w-1)
else:
    print(max_h+max_w)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [[0, i0]]
    D = [-1] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        d, i = hpop(h)
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    hpush(h, [nd, j])
                    D[j] = nd
    return [d if d >= 0 else 1<<100 for d in D]
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return [d if d >= 0 else 1<<100 for d in D]

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if D1[j] <= L:
            Y[i].append((j, 1))

# print("X =", X)
# print("Y =", Y)
D2 = []
for i in range(N):
    D2.append(dijkstra(N, Y, i))

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    a = D2[s][t]-1
    ans.append(str(a if a < 1 << 50 else -1))

print("\n".join(ans))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque
N, M, L = map(int, input().split())
D = [[1<<40] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j: continue
        if D[i][j] <= L:
            Y[i].append(j)
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D
D2 = []
for i in range(N):
    D2.append(BFS(N, Y, i))

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    a = D2[s-1][t-1]-1
    ans.append(str(a if a >= 0 else -1))
print("\n".join(ans))
### BUGGY CODE ###

s = list(input().strip())
n = len(s)
end = n - 2

count = 0

if n >= 3:
  i = 0
  while i < end:
    if s[i] == 'A' and s[i + 1] == 'B' and s[i + 2] == 'C':
      s[i] = 'B'
      s[i + 1] = 'C'
      s[i + 2] = 'A'
      count = count + 1

      j = i - 1
      while j >= 0 and s[j] == 'A':
        s[j] = 'B'
        s[j + 1] = 'C'
        s[j + 2] = 'A'
        count = count + 1
        j = j - 1

      i = i + 2
    else:
      i = i + 1

print(count)

### FIXED CODE ###

s = input().strip().replace('BC', 'D')
n = len(s)

count = 0
a_count = 0
for i in range(n):
  if s[i] == 'A':
    a_count += 1
  elif a_count > 0 and s[i] == 'D':
    count += a_count
  else:
    a_count = 0

print(count)
### BUGGY CODE ###

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

distance_list =[]


for i in range(1,n):
    for j in range(i+1,n+1):
        a = j - i
        b = abs(i - x) + abs(j-y) + 1
        if a <= b:
            distance_list.append(a)
        else:
            distance_list.append(b)

count_list = []

for i in range(n-1):
    count_list.append(distance_list.count(i+1))

for i in range(n-1):
    print(count_list[i])

### FIXED CODE ###

n,x,y = map(int,input().split())

distance_list =[0]*n

for i in range(1,n):
    for j in range(i+1,n+1):
        a = j - i
        b = abs(i - x) + abs(j-y) + 1
        distance_list[min(a,b)] += 1

for i in range(1,n):
    print(distance_list[i])
### BUGGY CODE ###

mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

C = [0] * (max(A) + 1)
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in enumerate(C):
    L *= pow(i, c, mod)
L %= mod

print(L * sum(pow(a, mod - 2, mod) for a in A) % mod)


### FIXED CODE ###

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(k):
  if a>0:
    a-=1
  elif b>0:
    b-=1
print(a,b)

### FIXED CODE ###

a,b,k=map(int,input().split())
if a>=k:
  print(a-k,b)
elif a+b>=k:
  print(0,b+a-k)
else:
  print(0,0)
### BUGGY CODE ###

# Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True


def same(x, y):
    return find(x) == find(y)


def size(x):
    return -par[find(x)]


N = int(input())
X = []
Y = []
Branch = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, i))
    Y.append((y, i))
X.sort()
Y.sort()
for X1, X2 in zip(X, X[1:]):
    Branch.append((X2[0] - X1[0], X1[1], X2[1]))
for Y1, Y2 in zip(Y, Y[1:]):
    Branch.append((Y2[0] - Y1[0], Y1[1], Y2[1]))
Branch.sort()

# 負のとき size, 非負のとき parent
par = [-1] * N
ans = 0
for c, a, b in Branch:
    if N <= 1:
        break
    if not same(a, b):
        unite(a, b)
        ans += c
        N -= 1

print(ans)



### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
                self.size[x] += self.size[y]
                self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def siz(self, x):
        x = self.find(x)
        return self.size[x]


N = int(input())
UF = UnionFind(N)
X = []
Y = []
Branch = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, i))
    Y.append((y, i))
X.sort()
Y.sort()
for X1, X2 in zip(X, X[1:]):
    Branch.append((X2[0] - X1[0], X1[1], X2[1]))
for Y1, Y2 in zip(Y, Y[1:]):
    Branch.append((Y2[0] - Y1[0], Y1[1], Y2[1]))
Branch.sort()

# 負のとき size, 非負のとき parent
par = [-1] * N
ans = 0
for c, a, b in Branch:
    if N <= 1:
        break
    if not UF.same_check(a, b):
        UF.union(a, b)
        ans += c
        N -= 1

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

from sys import stdin
import itertools

def main():

    input = stdin.readline

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

    mod = (10 ** 9) +7

    ans = 0

    for i,j in itertools.combinations(range(N),2):
        ans = (ans +  (A[i] * A[j])) % mod

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin
import itertools

def main():

    input = stdin.readline

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

    mod = (10 ** 9) +7

    ans = 0

    total = sum(A)

    for i in range(N):
        total = total - A[i]
        ans = (ans + (A[i] * total)) % mod
        

    print(ans)


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

# coding: utf-8
# Your code here!
n = int(input())
L = list(map(int,input().split()))
a = 1
for i in L:
    a = a*i

if a <= 10**18:
    print(a)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
L = list(map(int,input().split()))
a = 1
L = sorted(L)
for i in L:
    a = a*i
    if a == 0:
        break
    if a > 10**18:
        break
 
if a <= 10**18:
    print(a)
else:
    print(-1)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
q = []
for i in range(N):
  if A[i] in q:
    q.remove(A[i])
  else:
    q.append(A[i])
print(len(q))


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
c = 1
ans = 0
for i in range(N-1):
  if A[i] == A[i+1]:
    c += 1
  else:
    if c % 2 == 1:
      ans += 1
    c = 1
if c % 2 == 1:
  ans += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush
import numpy as np


def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) > 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) <= 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            import numpy as np
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

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

# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = np.zeros((N+1, S+1), np.int32)  # dp[i][j]はi個選んだ合計jの個数
dp[0][0] = 1
for a in A:
    for i in range(N-1, -1, -1):
        dp[i+1][a:] += dp[i][:-a]

dpS = dp[:, S]
answer = 0
power = 1
for x in dpS[1:][::-1]:
    answer += power * x
    answer %= MOD
    power *= 2; power %= MOD
print(answer%MOD)


### FIXED CODE ###

# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
dp = np.zeros(S+1, np.int64)
dp[0] = 1
for a in A:
    prev = dp.copy()
    dp[a:] += dp[:-a]
    dp += prev
    dp %= MOD

answer = dp[S]
print(answer%MOD)
### BUGGY CODE ###

s=int(input())
a=[]
a.append(s)
for i in range(10**6):
    if s%2==0:
        s//=2
        a.append(s)
    else:
        s=3*s+1
        a.append(s)
for i in range(10**6):
    for j in range(i+1,10**6):
        if a[i]==a[j]:
            print(j+1)
            exit(0)


### FIXED CODE ###

s=int(input())
a=[]
a.append(s)
for i in range(10**6):
    if s%2==0:
        s//=2
        if s in a:
            print(i+2)
            break
        else:
            a.append(s)
    else:
        s=3*s+1
        if s in a:
            print(i+2)
            break
        else:
            a.append(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():

    N, K = [int(i) for i in input().strip().split()]
    hights = [int(i) for i in input().strip().split()]
    min_costs = [10000*N] * N
    min_costs[0] = 0

    for i in range(N):
        for j in range(1, K+1):
            if j <= i:
                min_costs[i] = min(
                    min_costs[i - j] + abs(hights[i] - hights[i - j]), min_costs[i])
            else:
                break
    return min_costs[-1]


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

class Solver():
    def __init__(self, N, costs, K):
        self.dp = [99999999999] * N
        self.dp[0] = 0
        self.K = K
        self.costs = costs

    def solve(self):
        for i in range(0, len(self.costs)):
            for k in range(1, self.K + 1):
                if i >= k:
                    self.dp[i] = min(
                        self.dp[i - k] + abs(self.costs[i] - self.costs[i-k]), self.dp[i])
        return self.dp[-1]


def main():
    N, K = [int(i) for i in input().split()]
    costs = [int(i) for i in input().split()]
    solver = Solver(N, costs, K)
    print(solver.solve())


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

def resolve():
    n, m = map(int, input().split())
    li_broken = [int(input()) for _ in range(m)]
    dp = [0] * (n + 2)

    for i in reversed(range(n + 1)):

        if i == n:
            dp[i] = 1
            continue

        if i in li_broken:
            dp[i] = 0
            continue

        dp[i] = dp[i+1] + dp[i+2]

    print(dp[0] % 1000000007)
    
resolve()

### FIXED CODE ###

def step(n):
  if n == 0:
      return 1
  steps = [0 for i in range(n + 2)]
  steps[1] = 1
  steps[2] = 2
  for i in range(3, n + 1):
    steps[i] = steps[i - 1] + steps[i - 2]
  return steps[n]

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

a.append(n)

sum = 1

for i in range(m + 1):

  if i == 0:
    sum *= step(a[i] - 1)
    continue
  
  elif i == m:
    sum *= step(a[m] - a[m-1] -1)
    
  elif a[i] - a[i-1] == 1:
    sum = 0
    break

  else:
    sum *= step(a[i] - a[i-1] -2)
    
if m == 0:
  sum = step(n)

print(sum % 1000000007)
### BUGGY CODE ###

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

for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k] and j-i != k-j:
                c += 1
print(c)

### FIXED CODE ###

n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')
ans = r * g * b

for i in range(n):
    for j in range(i+1,n):
        if s[i] == s[j]:
            continue
        k = 2*j - i
        if k >= n or s[k] == s[i] or s[k] == s[j]:
            continue
        ans -= 1
        
print(ans)
### BUGGY CODE ###

n = int(input())
c = 1
a = list(map(int,input().split()))
for i in range(0,n):
  c *= a[i]
if c > 1000000000000000000:
  print(-1)
else:
  print(c)

### FIXED CODE ###

import sys
n = int(input())
c = 1
a = list(map(int,input().split()))
ok = 0;
for i in range(0,n):
    c *= a[i]
    if c > 1000000000000000000:
        ok = 1
        break
for i in range(0,n):
    if a[i] == 0:
        ok = 0
        c = 0
if (ok):
    print(-1)
else:
    print(c)
### BUGGY CODE ###

N = int(input())
list = [b for b in input().split()]
a = 1
for l in range(N):
    a = a*int(list[l-1])
if a > 10**18:
    print(-1)
else:
    print(a)

### FIXED CODE ###

N = int(input())
list = [b for b in input().split()]
a = 1
if "0" in list:
    print(0)
else:
    for l in range(N):
        a = a*int(list[l])
        if a > 10**18:
            print(-1)
            break
    else:
        print(a)
### BUGGY CODE ###

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

for j in range(A,B+1):
    if j < A + K or B - K < j:
        print(j)

### FIXED CODE ###

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

for j in range(A,A+K):
    if B >= j:
        print(j)

for j in range(B-K+1,B+1):
    if A + K - 1 < j :
        print(j)