Harryxun/stf_run huggingface dataset:
# seishin.py
N = int(input())
*X, = map(int, input().split())
L = int(input())

K = N.bit_length()

D = [[-1] for i in range(N)]
j = N-1
for i in range(N-1, -1, -1):
    while j > 0 and X[j] - X[i] > L:
        j -= 1
    D[i][0] = j
v = 2
for k in range(K):
    for i in range(N-v):
        if i + v < N and len(D[D[i][k]]) == k+1:
            D[i].append(D[D[i][k]][k])
    v <<= 1
def solve(a, b):
    if not a < b:
        a, b = b, a
    res = 1
    v = 2**K
    for k in range(K, -1, -1):
        if a + v < N-1 and D[a][k] < b:
            a = D[a][k]
            res += v
        v >>= 1
    return res
Q = int(input())
ans = []
for i in range(Q):
    a, b = map(int, input().split())
    ans.append(solve(a-1, b-1))
print(*ans, sep='\n')


### FIXED CODE ###

# seishin.py
N = int(input())
*X, = map(int, input().split())
L = int(input())

K = 20

D = [[N]*(K+1) for i in range(N)]
j = N-1
for i in range(N-1, -1, -1):
    while j > 0 and X[j] - X[i] > L:
        j -= 1
    D[i][0] = j
for k in range(K):
    for i in range(N):
        if D[i][k] != N:
            D[i][k+1] = D[D[i][k]][k]
def solve(a, b):
    if not a < b:
        a, b = b, a
    res = 1
    for k in range(K, -1, -1):
        if D[a][k] < b:
            a = D[a][k]
            res += 2**k
    return res
Q = int(input())
ans = []
for i in range(Q):
    a, b = map(int, input().split())
    ans.append(solve(a-1, b-1))
print(*ans, sep='\n')
#!/usr/bin/env python
# -*- coding:utf-8 -*-
import sys
import io
import re
import math

while True:
#    i = 0
    n = int(raw_input())
    l = map(float, raw_input().split())
    if n==0: break
# hyojunhensa**2 = sum(tokuten-heikinten)**2)/ninzu
    avg=sum(l)/len(l)
    naka=0
    for i in l:
        naka+=(i-avg)**2
    hyo2 = naka/n
    print (hyo2)**0.5

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-
import sys
import io
import re
import math

while True:
#    i = 0
    n = int(raw_input())
    if n==0: break
    l = map(float, raw_input().split())
# hyojunhensa**2 = sum(tokuten-heikinten)**2)/ninzu
    avg=sum(l)/len(l)
    naka=0
    for i in l:
        naka+=(i-avg)**2
    hyo2 = naka/n
    print (hyo2)**0.5
a,b,c = map(int,input().split())
l = [a,b,c]
l.sort()
if l[0] + 1[1] == 1[2]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b,c = map(int,input().split())
l = [a,b,c]
l.sort()
if l[0] + l[1] == l[2]:
  print("Yes")
else:
  print("No")
N = str(input())
list=[]
for i in range(N):
    list.append(int(input()))
count=0
X=list[0]
while True:
    X=list[X-1]
    count+=1
    if X == 2:
        print(count+1)
    if count == 100000:
        print(-1)

### FIXED CODE ###

N = int(input())
list=[]
for i in range(N):
    list.append(int(input()))
count=0
X=list[0]
while True:
    count+=1
    if X == 2:
        print(count)
        break
    elif count == N:
        print(-1)
        break
    X=list[X-1]
if __name__ == "__main__":
    n, m, x = map(int, input().split())

    c = []
    a = []

    for _ in range(n):
        cost, *rikaido = map(int, input().split())
        c.append(cost)
        a.append(rikaido)

    INF = float("inf")
    ans = INF
    
    for bit in range(1 << n):
        price_total = 0
        learn_total = [0] * m

        for i in range(n):
            if (bit >> i) & 1:
                # 買う場合
                price_total += c[i]
                for j in range(m):
                    learn_total[j] += a[i][j] 
        
        # 判定
        judge = True
        for j in range(m):
            if learn_total[j] < x:
                judge = False
                break
        
        if judge:
            ans = min(ans, price_total)
        
    if ans == INF:
        print(-1)
    else:
        print(ans)


### FIXED CODE ###

S=input()
T=input()

if len(S)+1==len(T) and T.startswith(S):
    print("Yes")
else:
    print("No")
a,b = map (int,input().sp;it())
print((a + b)//2)

### FIXED CODE ###

a,b = map (int,input().split())
print(-((-a - b)//2))
[print("{0:.3f} {1:.3f}".format(
	(k[2] - k[1] * ((k[0] * k[5] - k[2] * k[3]) / (k[0] * k[4] - k[1] * k[3]))) / k[0],
	((k[0] * k[5] - k[2] * k[3]) / (k[0] * k[4] - k[1] * k[3])))
) for i in sys.stdin for k in [int(j) for j in i.split()]]

### FIXED CODE ###

import sys
[print("{0:.3f} {1:.3f}".format((k[2] - k[1] * ((k[0] * k[5] - k[2] * k[3]) / (k[0] * k[4] - k[1] * k[3]))) / k[0], ((k[0] * k[5] - k[2] * k[3]) / (k[0] * k[4] - k[1] * k[3])))) for i in sys.stdin for k in [[int(float(j)) for j in i.split()]]]
X = int(input())
if (D == 25):
    print("Christmas")
elif (D == 24):
    print("Christmas Eve")
elif (D == 23):
    print("Christmas Eve Eve")
else:
    print("Christmas Eve Eve Eve")

### FIXED CODE ###

D = int(input())
if (D == 25):
    print("Christmas")
elif (D == 24):
    print("Christmas Eve")
elif (D == 23):
    print("Christmas Eve Eve")
else:
    print("Christmas Eve Eve Eve")
a_index, a_v = map(float, input().split())
b_index, b_v = map(float, input().split())
t = input()
 
d = abs(b_index - a_index)
d_v = abs(b_v - a_v)

if (d == 0) :
  print("YES")
elif (d_v != 0 and d / d_v <= t) :
  print("YES")
else :
  print("NO")

### FIXED CODE ###

a_index, a_v = map(int, input().split())
b_index, b_v = map(int, input().split())
t = int(input())
 
d = abs(b_index - a_index)
d_v = a_v - b_v
 
if d == 0 :
  print("YES")
elif d_v > 0 and d / d_v <= t :
  print("YES")
else :
  print("NO")
import numpy as np

H, W, M = map(int, input().split())
h = np.zeros(H)
w = np.zeros(W)
m = np.zeros((H, W))
ans = 0
'''
for _ in range(M):
    tmp_h, tmp_w = map(int, input().split())
    h[tmp_h-1] += 1
    w[tmp_w-1] += 1
    m[tmp_h-1, tmp_w-1] = 1.

h_max = np.max(h)
h_max_index = list(zip(*np.where(h == h_max)))
w_max = np.max(w)
w_max_index = list(zip(*np.where(w == w_max)))

for i in h_max_index:
    for j in w_max_index:
        if m[i[0]][j[0]] == 1.:
            tmp = h_max + w_max -1
        else:
            tmp = h_max + w_max
        if ans < tmp:
            ans = tmp
'''
print(int(ans))


### FIXED CODE ###

import numpy as np

H, W, M = map(int, input().split())
h = np.zeros(H)
w = np.zeros(W)
m = {}
flag = 0

for _ in range(M):
    tmp_h, tmp_w = map(int, input().split())
    h[tmp_h-1] += 1
    w[tmp_w-1] += 1
    m[(tmp_h-1, tmp_w-1)] = 1.

h_max = np.max(h)
h_max_index = list(zip(*np.where(h == h_max)))
w_max = np.max(w)
w_max_index = list(zip(*np.where(w == w_max)))

for i in h_max_index:
    for j in w_max_index:
        if (i[0], j[0]) not in m.keys():
            flag = 1
            break

if flag == 1:
    print(int(h_max + w_max))
else:
    print(int(h_max + w_max - 1))
k = int(input())

A = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(A[k + 1])

### FIXED CODE ###

k = int(input())

A = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(A[k - 1])
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
    for x in neighbor[p]:
        if x!=par[p]:
            par[x]=p
            descend[p]+=cur(x)
    return descend[p]

def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%mod
ans[1]=ans1

cur2(1)

for i in range(1,n+1):
    print(ans[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
    if neighbor[p]==[]: return
    for x in neighbor[p]:
        par[x]=p
        neighbor[x].remove(p)
        cur(x)
    descend[par[p]]+=descend[p]

def cur2(p):
    for x in neighbor[p]:
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[set()  for _ in range(n+2)]
descend=[1 for i in range(n+1)]
par=[0]+[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].add(b)
    neighbor[b].add(a)

cur(1)


ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

for i in range(1,n+1):
    print(ans[i])
import sys
import numpy as np
input = sys.stdin.readline

n, k = map(int, input().split())
parr = list(map(int, input().split()))
carr = list(map(int, input().split()))

dp = np.zeros((k+1, n))
maximum = -10**9

for i in range(1, k+1):
    for j in range(n):
      tmp = dp[i-1][j] + carr[j]
      dp[i][parr[j]-1] = tmp
      if tmp > maximum:
        maximum = tmp

print(int(maximum))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
parr = list(map(int, input().split()))
carr = list(map(int, input().split()))
scores = []

for i in range(n):
  cur = i
  # 1ループで通るノードの数とスコア
  roop_num = 0
  roop_score = 0
  while True:
    cur = parr[cur] - 1
    roop_num += 1
    roop_score += carr[cur]
    if cur == i:
      break
  tmp_max = -10**9
  # ループしたときにスコアが減るとき
  # kが1ループの回数より小さいとき
  if roop_score <= 0:
    score = 0
    max_iter = roop_num
  elif k <= roop_num:
    score = 0
    max_iter = k
  else:
    # ループする回数
    num = k // roop_num - 1
    score = roop_score*num
    max_iter = k - roop_num*num
  cur = i
  for _ in range(max_iter):
      cur = parr[cur] - 1
      score += carr[cur]
      if score > tmp_max:
        tmp_max = score
  scores += [tmp_max]

print(max(scores))
N = int(input())
S = input().split(' ')
s = sum([S[i-1] == S[i] or S[i] == S[i+1] for i in  range(1, N-1, 2)])
s -= sum([S[i-1]== S[i] == S[i+1] for i in  range(2, N, 2)])
print(s, flush=True)

### FIXED CODE ###

N = int(input())
S = input().split()
s = 0
for i in range(1, N):
	if S[i-1] == S[i]:
		S[i] = N + 1000000000
		s += 1
	
print(s, flush=True)
#coding:utf-8
import numpy as np
import collections
N = int(input())
arr = []
for n in range(N):
    arr.append(list(map(int,input().split())))
arr = np.array(arr)
x_min  = arr[:,0].min()
x_max = arr[:,0].max()
y_min = arr[:,1].min()
y_max =  arr[:,1].max()
mx = arr[:,2].max()
s = max(dx,dy)+1
for k in range(mx+100,mx-1,-1):
    for i in range(x_min,x_max+1):
        for j in range(y_min,y_max+1):
            for x,y,h in arr:
                h_ = max(k-abs(i-x)-abs(j-y),0)
                if h_ != h:
                    break
            else:
                print (i,j,k)
                exit()


### FIXED CODE ###

#coding:utf-8
import numpy as np
import collections
N = int(input())
arr = []
for n in range(N):
    arr.append(list(map(int,input().split())))
narr = np.array(arr)
x_min  = narr[:,0].min()
x_max = narr[:,0].max()
y_min = narr[:,1].min()
y_max =  narr[:,1].max()
mx = narr[:,2].max()
for k in range(mx+100,mx-1,-1):
    for i in range(x_min,x_max+1):
        for j in range(y_min,y_max+1):
            for x,y,h in arr:
                h_ = max(k-abs(i-x)-abs(j-y),0)
                if h_ != h:
                    break
            else:
                print (i,j,k)
                exit()
import math
from functools import reduce

mod = 10**9 + 7

def lcm(a, b):
	return a * b // math.gcd(a, b)


N = int(input())
A = [i for i in map(int, input().split())]

ans = reduce(lcm, A)


B = [ans//i for i in A]

ans = reduce(math.gcd, B)
if ans != 1:
	B_ = [i//ans for i in B]
	print(sum(B_) % mod)
else:
	print(sum(B) % mod)


### FIXED CODE ###

#from math import gcd
from fractions import gcd
from functools import reduce

mod = 10**9 + 7

def lcm(a, b):
	return a * b // gcd(a, b)


N = int(input())
A = [i for i in map(int, input().split())]

ans = reduce(lcm, A)

#print(ans)
B = [ans//i for i in A]

print(sum(B) % mod)
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import json
from copy import deepcopy

def dfs(graph, s, d, count=0):
  if len(graph[s]) == 0:
    # print(count)
    d[s] = count
  for t in graph[s]:
    if s in graph[t]:
      graph[t].remove(s)
    # print(s, t)
    dfs(graph, t, d, count+1)

if __name__=='__main__':
  graph = defaultdict(list)
  n, u, v = map(int, input().strip().split())
  for _ in range(n-1):
    ai, bi = map(int, input().strip().split())
    graph[ai].append(bi)
    graph[bi].append(ai)
  du, dv = dict(), dict()
  du[u], dv[v] = 0, 0
  dfs(deepcopy(graph), u, du)
  dfs(deepcopy(graph), v, dv)
  # print(json.dumps(du, indent=2))
  # print(json.dumps(dv, indent=2))

  costv = []
  for k in dv.keys():
    if k in du and du[k] < dv[k]:
      costv.append(dv[k])
  print(max(costv) - 1)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import json
from copy import deepcopy
import sys
sys.setrecursionlimit(10**4)

def dfs(graph, s):
  dist = [-1 for _ in range(len(graph))]
  dist[s] = 0
  stack = [s]
  while len(stack) != 0:
    s = stack.pop()
    for t in graph[s]:
      dist[t] = dist[s]+1
      if s in graph[t]:
        graph[t].remove(s)
      stack.append(t)
  return dist

if __name__=='__main__':
  graph = defaultdict(list)
  n, u, v = map(int, input().strip().split())
  for _ in range(n-1):
    ai, bi = map(int, input().strip().split())
    graph[ai-1].append(bi-1)
    graph[bi-1].append(ai-1)
  du = dfs(deepcopy(graph), u-1)
  dv = dfs(deepcopy(graph), v-1)
  costv = [0]
  for duv, dvv in zip(du, dv):
    if duv < dvv:
      costv.append(dvv)
  print(max(costv) - 1)
import bisect
def lis(A):
    n = len(A)
    L = [0] * n
    L[0] = A[0]
    length = 1

    for i in xrange(1, n):
        if L[length - 1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            L[bisect.bisect_left(L, A[i])] = A[i]

    return length

n = int(raw_input())
a = [int(raw_input()) for i in xrange(n)]
print lis(a)

### FIXED CODE ###

import bisect
def lis(A):
    n = len(A)
    L = [0] * n
    L[0] = A[0]
    length = 1

    for i in xrange(1, n):
        if L[length - 1] < A[i]:
            L[length] = A[i]
            length += 1
        else:
            L[bisect.bisect_left(L[:length], A[i])] = A[i]

    return length

n = int(raw_input())
a = [int(raw_input()) for i in xrange(n)]
print lis(a)
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        self.parents[y] = x
        self.parents[x] = x
        self.sizes[x] += self.sizes[y]
        self.sizes[y] = self.sizes[x]

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if y < x:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

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

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


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)
import sys
n = input()
for i in n:
	if i == '7'
		print('Yes')
		sys.exit(0)
print('No')



### FIXED CODE ###

import sys
n = input()
for i in n:
	if i == '7':
		print('Yes')
		sys.exit(0)
print('No')
a,b,c=[int(i) for i in input().split()]
print("YES" if a[-1]==b[0] and b[-1]== c[0] else "NO")

### FIXED CODE ###

a,b,c=input().split()
print("YES" if a[-1]==b[0] and b[-1]== c[0] else "NO")
n = int(input())
ACs = 0
WAs = 0
TLEs = 0
REs = 0
for i in range(n):
  result = input()
  if result == "AC":
    ACs += 1
  elif result == "WA":
    WAs += 1
  elif result == "TLE":
    TLEs += 1
  else:
    REs += 1
print("AC x " + ACs)
print("WA x " + WAs)
print("TLE x " + TLEs)
print("RE x " + REs)

### FIXED CODE ###

n = int(input())
ACs = 0
WAs = 0
TLEs = 0
REs = 0
for i in range(n):
  result = input()
  if result == "AC":
    ACs += 1
  elif result == "WA":
    WAs += 1
  elif result == "TLE":
    TLEs += 1
  else:
    REs += 1
print("AC x " + str(ACs))
print("WA x " + str(WAs))
print("TLE x " + str(TLEs))
print("RE x " + str(REs))
size = 500000
mod = 10 ** 9 + 7
fac = [0] * size
finv = [0] * size
inv = [0] * size

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, size):
    fac[i] = fac[i-1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i-1] * inv[i] % mod

def nPr(n, r, mod):
    if n < 0 or r < 0 or n < r:
        return 0
    return fac[n] * finv[n-r] % mod

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, size + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def nCr(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

ans = 0
flag = 1

for k in range(N+1):
    ans += flag * nPr(M - k, N - k, mod) * nCr(N, k, mod) * nPr(M, N, mod)
    flag *= -1
    ans %= mod

print(ans)

### FIXED CODE ###

size = 500001
mod = 10 ** 9 + 7
fac = [0] * size
finv = [0] * size
inv = [0] * size

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, size):
    fac[i] = fac[i-1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i-1] * inv[i] % mod

def nPr(n, r, mod):
    if n < 0 or r < 0 or n < r:
        return 0
    return fac[n] * finv[n-r] % mod

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, size + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def nCr(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

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

ans = 0
flag = 1

for k in range(N+1):
    ans += flag * nPr(M - k, N - k, mod) * nCr(N, k, mod) * nPr(M, N, mod)
    flag *= -1
    ans %= mod

print(ans)
n,m,l=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]
B=[list(map(int,input().split())) for i in range(m)]
C=[[0]*l for i in range(n)]

for x in range(n):
    for y in range(m):
        for z in range(l):
            C[x][y] += A[x][z]*B[z][y]

for row in range(n):
    print("%d"%(C[row][0]),end="")
    for col in range(1,l):
        print(" %d"%(C[row][col]),end="")
    print()



### FIXED CODE ###

n,m,l=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]
B=[list(map(int,input().split())) for i in range(m)]
C=[[0]*l for i in range(n)]

for x in range(n):
    for y in range(l):
        for z in range(m):
            C[x][y] += A[x][z]*B[z][y]

for row in range(n):
    print("%d"%(C[row][0]),end="")
    for col in range(1,l):
        print(" %d"%(C[row][col]),end="")
    print()
s=list(map(int,input().split()))
num=1
cost=s[0]
while cost < s[1]:
  num=num+1
  cost=num*s[0]-1
print(num)
  

### FIXED CODE ###

s=input()
t=input()
result=0
if s[:1]==t[:1]:
    result=result+1

if s[1:2]==t[1:2]:
    result=result+1

if s[2:3]==t[2:3]:
    result=result+1
print(result)
#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = input()
S = raw_input.split()
for i in range(N):
	if S[i] == 'Y':
		print('Four')
		N = -1
		break
if N == -1:print('Three')

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

N = input()
S = raw_input().split()
for i in range(N):
	if S[i] == 'Y':
		print('Four')
		N = -1
		break
if N > -1:
	print('Three')
n=int(input())
lista = [int(i) for i in input().split()]

import fractions

list_ans=[]

for i in range(n):
	listb=lista.copy()
	listb.pop(i)
#	print(listb)

	ans= listb[0]

	for i in range(1,n-1):
		ans=fractions.gcd(ans,listb[i])
#	print(ans)
	list_ans.append(ans)

print(int(max(list_ans)))


	

### FIXED CODE ###

n=int(input())
lista = [int(i) for i in input().split()]

import fractions
import copy

listb=[]
listc=[]
ansb= lista[0]

for i in range(1,n-1):
	ansb=fractions.gcd(ansb,lista[i])
#	print(ansb)
	listb.append(ansb)

#print(int(max(list_ans)))
ansc= lista[n-1]

for i in range(n-2,0,-1):
	ansc=fractions.gcd(ansc,lista[i])
#	print(ansc)
	listc.append(ansc)


list_b=[lista[0]]
listb=[1]+list_b+listb
list_c=[lista[n-1]]
listc=list(reversed(listc))+list_c+[1]
#print(listb)
#print(listc)

ans=0
list_ans=[listc[0],listb[n-1]]
for i in range(1,n-1):
	ans=fractions.gcd(listb[i],listc[i])
	list_ans.append(ans)
	
ansans=max(list_ans)

if n==2:
	ansans=max(lista[0],lista[1])
	
print(ansans)
n, m = [int(i) for i in input().split()]
cnt = 0
for i in input().split();
	if m <= int(i):
    	cnt += 1
print(cnt)

### FIXED CODE ###

n, m = [int(i) for i in input().split()]
cnt = 0
for i in input().split():
  if m <= int(i):
    cnt+=1
print(cnt)
s = list(input())
print(s[0] + (s.count - 2) + s[-1])

### FIXED CODE ###

S = input()
print(S[0] + str(len(S)-2) + S[len(S)-1])
import sys
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))

sys.setrecursionlimit(10 ** 9)


def main():
    N, M = MAP()
    X = LIST()
    
    if M == 1:
        print(0)
        sys.exit()
        
    X = sorted(X)

    H = []
    heapify(H)
    for i in range(len(X)-1):
        heappush(H, (X[i+1] - X[i])*(-1))

    for i in range(N-1): heappop(H)
    
    print(sum(H)*(-1))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))

sys.setrecursionlimit(10 ** 9)


def main():
    N, M = MAP()
    X = LIST()

    if M == 1 or N >= M:
        print(0)
        sys.exit()

    X = sorted(X)

    H = []
    heapify(H)
    for i in range(len(X)-1):
        heappush(H, (X[i+1] - X[i])*(-1))

    for i in range(N-1): heappop(H)

    print(sum(H)*(-1))


if __name__ == '__main__':
    main()