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

from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((-1,tmp_dict[C[i]],i))
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i
    
  #assert time() - start < 0.2

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = map(int,input().split())
    # (元のクエリの順番、l, r)
    X.append((i,l-1,r-1))

  #assert time() - start < 0.8
    
  X.extend(res) 
  X = sorted(X,key=lambda x:(x[1],-x[0]))
  
  assert time() - start < 0.5

  # 平面走査
  bit = BIT(N)
  ans=[]
  for idx,l,r in reversed(X):
    if idx == -1:
      bit.add(r,1)
    else:
      ans.append((idx,r-l+1-bit.query(l-1,r)))

  # 元の順番にソートし直して出力
  print(*list(zip(*sorted(ans)))[1])
  
if __name__=="__main__":
  main()

### FIXED CODE ###

from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())
  q = [tuple(map(int,input().split())) for _ in range(Q)]

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((tmp_dict[C[i]]<<40) | (Q<<20) | i)
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = q[i]
    # (元のクエリの順番、l, r)
    X.append(((l-1)<<40) | (i<<20) | r-1)
    
  X.extend(res) 
  X = sorted(X)

  # 平面走査
  bit = BIT(N)
  ans=[0]*Q
  mask = (1<<20) - 1
  for l in reversed(X):
    r = l & mask
    l >>= 20
    idx = l & mask
    l >>= 20
    if idx == Q:
      bit.add(r,1)
    else:
      ans[idx] = r-l+1-bit.query(l-1,r)
      
  print(*ans)
  
if __name__=="__main__":
  main()
### BUGGY CODE ###

def main():
    n=int(input())
    s=[input() for _ in [0]*n]
    cnt=0
    for a in range(n):
        flag=0
        for i in range(n):
            i_n=i%n
            ia_n=(i+a)%n
            for j in range(i):
                if s[i_n][(j+a)%n]!=s[j%n][ia_n]:
                    flag=1
                    break
            if flag==1:
                break
        else:
            cnt+=1
    print(n*cnt)
main()

### FIXED CODE ###

def main():
    n=int(input())
    nn=2*n-1
    s=[input() for _ in [0]*n]
    s=[i+i[:-1] for i in s]+[i+i[:-1] for i in s][:-1]
    ans=[[0]*n for _ in [0]*n]
    for i in range(1,nn):
        m=min(i+1,n)
        for j in range(nn-1):
            for k in range(max(i-j-n,0)+1,min(m,nn-j,i-j+n)):
                ii=i-k
                if s[i][j]!=s[ii][j+k]:
                    l=min(n-k+1,ii,j)
                    width=l-max(-1,ii-n,j-n)
                    ans[ii-l][j-l]=max(ans[ii-l][j-l],width)
    for i in range(1,n):
        for j in range(1,n):
            ans[i][j]=max(ans[i][j],ans[i-1][j-1]-1)
    print(sum([sum([i==0 for i in a]) for a in ans]))
main()
### BUGGY CODE ###

N = int(input())

A = [0] * N
for i in range(N):
    a = int(input())
    A[i] = a

for i in range(N):
    tmp = A[:]
    ans = max(tmp)
    if ans == A[i]:
        ans = sorted(tmp)[-2]
    print(ans)   

### FIXED CODE ###

N = int(input())

A = [0] * N
for i in range(N):
    a = int(input())
    A[i] = a

tmp = A[:]
tmp.sort(reverse=True)
for i in range(N):
    
    if tmp[0] == A[i]:
        print(tmp[1])
    else:
        print(tmp[0])
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc127/tasks/abc127_d
# プライオリティキュー　解説を見ながら実装


import heapq

n, m = map(int, input().strip().split())

a = list(map(int, input().strip().split()))
a = list(map(lambda x: x*(-1), a))
for _ in range(m):
    b, c = map(int, input().strip().split())
    for _ in range(b):
        a.append(c * (-1))

heapq.heapify(a)
res = 0
for _ in range(n):
    res += heapq.heappop(a) * (-1)

print(res)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 問題：https://atcoder.jp/contests/abc127/tasks/abc127_d
# プライオリティキュー　解説を見ながら実装


import heapq

n, m = map(int, input().strip().split())

q = []
a = list(map(int, input().strip().split()))
for i in range(n):
    heapq.heappush(q,(a[i]*(-1), 1))
for i in range(m):
    b, c = map(int, input().strip().split())
    heapq.heappush(q,(c*(-1), b))

res = 0
for _ in range(n):
    c, b = heapq.heappop(q)
    res += c * (-1)
    if b > 1:
        b -= 1
        heapq.heappush(q, (c, b))

print(res)
### BUGGY CODE ###

def resolve():
    s=list(input())
    q=int(input())
    Q=[list(map(str,input().split())) for i in range(q)]

    #print(Q)

    for i in range(q):
        if int(Q[i][0])==1:
            s.reverse()
            #print(s)
        elif int(Q[i][0])==2:
            if int(Q[i][1])==1:
                s.insert(0,Q[i][2])
                #print(s)
            else:
                s.append(Q[i][2])
                #print(s)
    print(*s,sep='')






resolve()

### FIXED CODE ###

def resolve():
    from collections import deque
    d=deque()
    s=list(input())
    d.extend(s)
    #print(d)
    q=int(input())
    Q=[list(map(str,input().split())) for i in range(q)]

    reverse= False
    for i in range(q):
        if int(Q[i][0])==1:
            reverse=not reverse
        elif int(Q[i][0])==2:
            if int(Q[i][1])==1:
                if reverse:
                    d.append(Q[i][2])
                else:
                    d.appendleft(Q[i][2])
                #print(s)
            else:
                if reverse:
                    d.appendleft(Q[i][2])
                else:
                    d.append(Q[i][2])
                #print(s)

    if reverse:
        print(''.join(list(reversed(d))))
    else:
        print(''.join(list(d)))






resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    S = input().replace('\n', '')
    Q = int(input())

    for _ in range(Q):
        query = input().split()
        if len(query) == 1:
            S = S[::-1]
        else:
            T, F, C = query
            if int(F) == 1:
                S = C + S
            else:
                S = S + C
    print(S)


main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    S = input().replace('\n', '')
    Q = int(input())

    flg = 0
    head = ""
    tail = ""
    for _ in range(Q):
        query = input().split()
        if len(query) == 1:
            head, tail = tail, head
            flg += 1
        else:
            T, F, C = query
            if int(F) == 1:
                head += C
            else:
                tail += C
    if flg % 2:
        print(head[::-1] + S[::-1] + tail)
    else:
        print(head[::-1] + S + tail)
main()
### BUGGY CODE ###

# 各クエリに対して,二分探索で解を求める

def bs(x,li):
    # 値xがliの2連続した値a,b達が作る[a,b)のどこに入るか
    # aを返す
    # liはソート済みとする
    left,right=0,len(li)
    while left+1<right:
        mid = (left+right)//2
        if li[mid]<=x:
            left=mid
        else:
            right=mid
    return left

def get(L):
    ret=[-10**13]
    for _ in range(L):
        ret.append(int(input()))
    ret.append(10**13)
    return ret

A,B,Q=map(int,input().split())
S=get(A)
T=get(B)
for _ in range(Q):
    x=int(input())

    # sn,sp,tn,tpを二分探索で出す
    sn,tn=bs(x,S),bs(x,T)

    # これらの経路の組み合わせの中に最小値が含まれている
    # 全部で8パターンあるので全探索してminをansとして保持
    ans=10**13
    for s in [S[sn],S[sn+1]]:
        for t in [T[tn],T[tn+1]]:
            d=abs(s-x)+abs(t-s)
            e=abs(t-x)+abs(s-t)
            ans=min([ans,d,e])
    print(ans)

### FIXED CODE ###

# 各クエリに対して,二分探索で解を求める

def bs(x,li):
    # 値xがliの2連続した値a,b達が作る[a,b)のどこに入るか
    # aを返す
    # liはソート済みとする
    left,right=0,len(li)
    while left+1<right:
        mid = (left+right)//2
        if li[mid]<=x:
            left=mid
        else:
            right=mid
    return left

def get(L):
    ret=[-10**13]
    for _ in range(L):
        ret.append(int(input()))
    ret.append(10**13)
    return ret

A,B,Q=map(int,input().split())
S=get(A)
T=get(B)
for _ in range(Q):
    x=int(input())

    # sn,sp,tn,tpを二分探索で出す
    sn,tn=bs(x,S),bs(x,T)

    # これらの経路の組み合わせの中に最小値が含まれている
    # 全部で8パターンあるので全探索してminをansとして保持
    ans=10**13
    for s in [S[sn],S[sn+1]]:
        for t in [T[tn],T[tn+1]]:
            d=abs(s-x)+abs(t-s)
            e=abs(t-x)+abs(s-t)
            ans=min([ans,d,e])
    print(ans)
### BUGGY CODE ###

import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))

a_sorted = sorted(a)

while m > 0:
    maximum = a_sorted.pop(-1)
    if maximum % 2 == 0:
        bisect.insort_left(a_sorted, maximum//2)
    else:
        bisect.insort_left(a_sorted, maximum//2)
    m += -1
ans = sum(a_sorted)
print(ans)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a = list(map(lambda x : int(x) * (-1), input().split()))
heapq.heapify(a)

for i in range(m):
    maximum = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-maximum//2))
print(-sum(a))
### BUGGY CODE ###

from bisect import bisect_right
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0
for i in range(N):
	for j in range(bisect_right(B, A[i]), N):
		ans += N - bisect_right(C, B[j])
print(ans)


### FIXED CODE ###

from bisect import bisect_right, bisect_left

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

ans = 0

for bi in range(N):
    ai_max = bisect_left(A, B[bi])
    ci_min = bisect_right(C, B[bi])
    ans += (ai_max) * (N - ci_min)

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

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

a.sort()
if a[0] == 1:
    if len(a) == 1 or a[1] != 1:
        print(1)
    else:
        print(0)
else:
    a += [-1]
    ret = 0
    d_lst = []
    add = 1
    for i in range(n):
        if a[i] != a[i+1]:
            for d in d_lst:
                if a[i] % d == 0:
                    break
            else:
                ret += add
                d_lst.append(a[i])
                add = 1
        else:
            add = 0
    print(ret)


### FIXED CODE ###

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

a.sort()
if a[0] == 1:
    if len(a) == 1 or a[1] != 1:
        print(1)
    else:
        print(0)
else:
    a_max = a[-1]
    seive = [True for _ in range(a_max + 1)]
    a += [-1]
    ret = 0
    add = 1
    for i in range(n):
        if a[i] != a[i+1]:
            if seive[a[i]]:
                ret += add
                j = 2 * a[i]
                while j <= a_max:
                    seive[j] = False
                    j += a[i]
            add = 1
        else:
            add = 0
    print(ret)
### BUGGY CODE ###

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

def dec1(n):
    return n - 1

p = [b for _ in range(a)]
p1 = copy.deepcopy(p)
for i, name in enumerate(m):
    p1 = list(map(dec1, p1))
    p1[name-1] += 1

for i, name in enumerate(p1):
    if name <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

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

def dec1(n):
    return n - 1

p = [b-n]*a
p1 = copy.deepcopy(p)
for i, name in enumerate(m):
    p1[name-1] += 1

for i, name in enumerate(p1):
    if name <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

import math

K = int(input())

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            ans += math.gcd(a, math.gcd(b, c))
print(ans)

### FIXED CODE ###

import math

K = int(input())

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            ans += math.gcd(a, math.gcd(b, c))
print(ans)
### BUGGY CODE ###

n=int(input())
elements= input().split()
q=int(input())
actions=[]
for i in range(q):
    actions.append(input().split())
 
number_list=[]
count_list=[]
for e in elements:
    if int(e) in number_list:
        count_list[number_list.index(int(e))]+=1
    else:
        number_list.append(int(e))
        count_list.append(1)
 
sum=0
for i in range(len(count_list)):
    sum+=number_list[i]* count_list[i]

for act in actions:
    if int(act[0]) in number_list:
        index0=number_list.index(int(act[0]))
        
        if int(act[1]) in number_list:
            index1=number_list.index(int(act[1]))
            sum+=(number_list[index1]-number_list[index0])* count_list[index0]
            count_list[index1]+=count_list[index0]
        else:
            sum+=(int(act[1])-number_list[index0])* count_list[index0]
            number_list.append(int(act[1]))
            count_list.append(count_list[index0])

        number_list.pop(index0)
        count_list.pop(index0)
 
 
    print(str(sum))

### FIXED CODE ###

n=int(input())
elements= input().split()
q=int(input())
actions=[]
for i in range(q):
    actions.append(input().split())
 
dict={}
for e in elements:
    count=dict.get(e,0)
    count+=1
    dict[e]=count
 
sum=0
for key in dict.keys():
    sum+=int(key)* dict[key]

for act in actions:
    count=dict.get(act[0],0)
    sum+=(int(act[1])-int(act[0]))*count
    count+=dict.get(act[1],0)
    dict[act[1]]=count
    dict[act[0]]=0
 
    print(str(sum))
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    N,K = map(int, input().split())
    A = np.array(sorted([int(i) for i in input().split()]))

    zero_left = np.searchsorted(A, 0, side='left')
    zero_right = np.searchsorted(A, 0, side='right')

    negative = zero_left
    positive = N - zero_right
    zero = zero_right - zero_left
    non_posi = negative * positive + zero * (N - zero) + zero * (zero - 1) // 2

    if K <= negative * positive:
        Nega = A[:zero_left]
        Posi = A[zero_right:]

        left = -(A[0]**2)
        right = 0
        while right - left > 1:
            x = (left + right) // 2
            count = np.searchsorted(Nega, x // Posi, side='right').sum()

            if count < K:
                left = x
            else:
                right = x

        print(right)

    elif K <= non_posi:
        print(0)

    else:
        Nega = np.sort(np.abs(A[:zero_left]))
        Posi = A[zero_right:]

        left = 0
        right = 10**18
        while right - left > 1:
            x = (left + right) // 2
            count = 0
            count += np.searchsorted(Nega, x // Nega, side='right').sum()
            count += np.searchsorted(Posi, x // Posi, side='right').sum()
            count -= np.int_(np.where(np.searchsorted(Nega, x // Nega) >= np.arange(1,negative+1), True, False)).sum()
            count -= np.int_(np.where(np.searchsorted(Posi, x // Posi) >= np.arange(1,positive+1), True, False)).sum()
            count //= 2

            if count + non_posi < K:
                left = x
            else:
                right = x

        print(right)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    N,K = map(int, input().split())
    A = np.array(sorted([int(i) for i in input().split()]))

    negative = A[A < 0]
    positive = A[A > 0]
    ln = len(negative)
    lp = len(positive)
    zero = np.count_nonzero(A == 0)

    def count(x):
        count = 0
        if x >= 0:
            count += N * zero
        count += np.searchsorted(A, x // positive, side='right').sum()
        count += N * ln - np.searchsorted(A, -(-x // negative), side='left').sum()
        count -= np.count_nonzero(A * A <= x)
        count //= 2

        return count


    left = -(10**18)
    right = 10**18
    while right - left > 1:
        x = (left + right) // 2
        if count(x) < K:
            left = x
        else:
            right = x

    print(right)


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

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
import copy
Z = copy.deepcopy(A)
for i in range(1, N):
    Z.append(abs(A[i] - A[i - 1]))
Z.sort()
i = 0

while True:
    if i >= len(Z):
        break
    if Z[i] == 0:
        del Z[i]
        i -= 1
    elif i > 0 and Z[i] == Z[i - 1]:
        del Z[i]
        i -= 1
    i += 1

ans = -1

import fractions
gcd = Z[0]
#for i in range(1, len(Z)):
 #   gcd = fractions.gcd(gcd, Z[i])

if K % gcd == 0:
    ans = 1
    
if K > max(A):
    ans = -1
       
for i in A:
    if K == i:
        ans = 1
        break

if ans == -1:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
import copy
Z = copy.deepcopy(A)
#for i in range(1, N):
 #   Z.append(abs(A[i] - A[i - 1]))
Z.sort()
i = 0

while True:
    if i >= len(Z):
        break
    if Z[i] == 0:
        del Z[i]
        i -= 1
    elif i > 0 and Z[i] == Z[i - 1]:
        del Z[i]
        i -= 1
    i += 1

ans = -1

import fractions
gcd = Z[0]
for i in range(1, len(Z)):
    gcd = fractions.gcd(gcd, Z[i])

if K % gcd == 0:
    ans = 1
    
if K > max(A):
    ans = -1
       
for i in A:
    if K == i:
        ans = 1
        break

if ans == -1:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**18
def rec(z,w,now,t):
    global N
    if dic.get((z,w,now,t),None)!=None:
        return dic[(z,w,now,t)]
    if now==N-1:
        dic[(z,w,now,t)]=abs(z-w)
        return abs(z-w)
    if t==0:
        res=-INF
        for i in range(now+1,N):
            res=max(res,rec(a[i],w,i,1))
    elif t==1:
        res=INF
        for i in range(now+1,N):
            res=min(res,rec(z,a[i],i,0))
    dic[(z,w,now,t)]=res
    return res

N,Z,W=map(int,input().split())
a=list(map(int,input().split()))
dic={}

print(rec(Z,W,-1,0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**18

def main():
    N,Z,W=map(int,input().split())
    a=list(map(int,input().split()))
    dic={}
    def rec(z,w,now,t):
        if dic.get((now,t),None)!=None:
            return dic[(now,t)]
        if now>=N-1:
            return abs(z-w)
        if not t:
            res=-INF
            for i in range(now+1,N):
                r=rec(a[i],w,i,1)
                res=max(res,r)
        else:
            res=INF
            for i in range(now+1,N):
                r=rec(z,a[i],i,0)
                res=min(res,r)
        dic[(now,t)]=res
        return res

    return rec(Z,W,-1,0)
    
print(main())
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ap = [e + 1 for e in a]
am = [e - 1 for e in a]

b = sorted(a + ap + am)

cmax = 0

pre = b.pop(0)

while True:
    smc = 1
    while True:
        if len(b) == 0:
            print(cmax)
            import sys
            sys.exit()

        cur = b.pop(0)
        if cur == pre:
            smc += 1
        else:
            cmax = max(smc, cmax)
            pre = cur
            break



### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
ap = [e + 1 for e in a]
am = [e - 1 for e in a]

table = [0 for _ in range(10**5 + 2)]
for e in a:
    table[e + 1] += 1
    table[(e+1) + 1] += 1
    table[(e-1) + 1] += 1
print(max(table))
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
ans=0
for i in range(N-1):
	for j in range(i+1,N):
		ans+=(A[i]*A[j])
		ans=ans%(10**9+7)	
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
ans=0
SM=sum(A)
for i in range(N-1):
	SM-=A[N-1-i]
	ans+=A[N-i-1]*SM
	ans=ans%(10**9+7)
					
print(ans)
### BUGGY CODE ###

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

ans=""
for i in range(1,N+1):
    ans += " " + str(list.index(i)+1)
    
print(ans)

### FIXED CODE ###

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

dic={}
ans=""

for i in range(N):
    dic[list[i]]=i+1
    
for i in range(1, N+1):
    ans += " " + str(dic[i])
    
print(ans)
### BUGGY CODE ###

s = list(input())
answer = 0

for i in range(3, len(s)):
    for j in range(0, len(s) - i):
        num = int(''.join(s[j:(i + j + 1)]))
        if num % 2019 == 0:
            answer += 1

print(answer)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

n, m  = map(int, input().split())
alist = [int(input()) for i in range(m)]
div_num = 1000000007

f = [1, 1]
for i in range(n-1)[::-1]:
  flag1 = True if i+1 not in alist else False
  flag2 = True if i+2 not in alist else False
  if flag1 is False and flag2 is False:
    print(0)
    exit()
  elif flag1 is False and flag2 is True:
    f = [f[1]] + [f[0]]
  elif flag1 is True and flag2 is False:
    f = [f[0]] + [f[0]]
  else:
    f = [f[0]+f[1]] + [f[0]]
     
print(int(f[0]%div_num))

### FIXED CODE ###

n, m  = map(int, input().split())

if n == 1:
  print(1)
  exit()

f = [0 for i in range(n)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for i in range(n-2)[::-1]:
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

if f[0] != -1 and f[1] != -1:
  print(int((f[0]+f[1])%div_num))
elif f[0] == -1 and f[1] != -1:
  print(int(f[1]%div_num))
elif f[0] != -1 and f[1] == -1:
  print(int(f[0]%div_num))
else:
  print(0)
### BUGGY CODE ###

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

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

for i in range(N):
    if i == 0:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + abs(H[i]-H[i-1])
        for k in range(2,min(K,i)+1):
            dp[i] = min(dp[i-k] + abs(H[i]-H[i-k]),dp[i])

print(dp[N-1])


### FIXED CODE ###

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

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

for i in range(N):
    if i == 0:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + abs(H[i]-H[i-1])
        for k in range(2,min(K,i)+1):
            dp[i] = min(dp[i-k] + abs(H[i]-H[i-k]),dp[i])

print(dp[N-1])