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

def main():
    import bisect
    from array import array
    B=bisect.bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=t[-q:]
    N0=2**(q-1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in sorted((x,B(d,s-x)+N0,B(d,t-x)+N0)for s,t,x in zip(t[:-q:3],t[1:-q:3],t[2:-q:3]))[::-1]:
        while l<r:
            if r&1:
                r-=1
                data[r-1]=x
            if l&1:
                data[l-1]=x
                l+=1
            l>>=1
            r>>=1
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

t = input()
ans = ''
for i in range(len(t)):
    if t[i] == '?':
        ans += 'D'
    else:
        ans += t[i]
print(ans)


### FIXED CODE ###

t = input()
n = len(t)
ans = ''
for i in range(n):
    if t[i] == '?':
        ans += 'D'
    else:
        ans += t[i]
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3.6
import bisect
n = int(input())
x = [int(item) for item in input().split()]
l = int(input())
q = int(input())
ab = []
for i in range(q):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    if a > b:
        a, b = b, a
    ab.append((a, b))

dt = [[0] * n for _ in range(40)]
for i, item in enumerate(x):
    dt[0][i] = i
    dt[1][i] = bisect.bisect_right(x, item + l) - 1

for i in range(2, 40):
    for j in range(n):
        dt[i][j] = dt[i-1][dt[i-1][j]]

for a, b in ab:
    days = 0
    is_ok = False
    while a < b:
        for i in range(0, 40):
            if dt[i][a] >= b:
                if i == 1:
                    days += 1
                    is_ok = True
                else:
                    a = dt[i-1][a]
                    days += 2**(i-2)
                break
        if is_ok:
            break
    print(days)

### FIXED CODE ###

#!/usr/bin/python3.6
import bisect
n = int(input())
x = [int(item) for item in input().split()]
l = int(input())
q = int(input())
ab = []
for i in range(q):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    if a > b:
        a, b = b, a
    ab.append((a, b))

dt = [[0] * n for _ in range(40)]
for i, item in enumerate(x):
    dt[0][i] = i
    dt[1][i] = bisect.bisect_right(x, item + l) - 1

for i in range(2, 40):
    for j in range(n):
        dt[i][j] = dt[i-1][dt[i-1][j]]

for a, b in ab:
    days = 0
    is_ok = False
    while a < b:
        for i in range(0, 40):
            if dt[i][a] >= b:
                if i == 1:
                    days += 1
                    is_ok = True
                else:
                    a = dt[i-1][a]
                    days += 2**(i-2)
                break
        if is_ok:
            break
    print(days)
### BUGGY CODE ###

a, b, c, d = map(int, input().split())
ans = 0
for i in range(a, b+1):
  if i % c != 0 and i % d != 0:
    ans += 1
print(ans)    

### FIXED CODE ###

from math import gcd

a, b, c, d = map(int, input().split())
n = c * d // gcd(c,d)
x = (b // c) - ((a-1) // c)
y = (b // d) - ((a-1) // d)
z = (b // n) - ((a-1) // n)
print(b-a+1-(x+y-z))
### BUGGY CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

import string

def main():
    n,m = i_map()

    c = [[INF]*n for _ in range(n)]
    for i in range(n):
        c[i][i] = 0

    for _ in range(m):
        a,b = i_map()
        c[a-1][b-1] = 1
        c[b-1][a-1] = 1

    for i,k in enumerate(c[0]):
        pass
        if k == 1:
            if c[i][-1] == 1:
                print("POSSIBLE")
                exit()
    print("IMPOSSIBLE")





if __name__=="__main__":
    main()


### FIXED CODE ###

N, M = map(int, input().split())
L = [list(map(int, input().split())) for i in range(M)]
s = []
g = []
for i in range(M):
    if 1 == L[i][0]:
        s.append(L[i][1])
    if 1 == L[i][1]:
        s.append(L[i][0])
        
for i in range(M):
    if N == L[i][0]:
        g.append(L[i][1])
    if N == L[i][1]:
        g.append(L[i][0])
        
if set(g)&set(s):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

N=int(input())
count_list=[]
i=0
while(i<N):
    a=int(input())
    count_list.append(a)
    i+=1

i=0
while(i<N):
    b=[]
    for j in count_list:
        b.append(j)
    b[i]=0
    print(max(b))
    i+=1

### FIXED CODE ###

N=int(input())

max_index=-1
max_number=-1
second_number=-1
max_count=0
i=0
while(i<N):
    a=int(input())
    if(max_number<a):
        second_number=max_number
        
        max_number=a
        max_index=i
        max_count=0
    elif(max_number==a):
        max_count+=1
        max_index=-1
    elif(second_number<a):
        second_number=a
    i+=1

j=0
while(j<N):
    if(j==max_index and max_count==0):
        print(second_number)
    else:
        print(max_number)
    j+=1
### BUGGY CODE ###

N = int(input())
a = [''.join(sorted(list(input()))) for i in range(N)]
a_unique = set(a)
b = 0
for i in a_unique:
    c = a.count(i)
    b = b + c * (c - 1) / 2
print(int(b))


### FIXED CODE ###

from collections import Counter

N = int(input())
a = [''.join(sorted(input())) for i in range(N)]
count = Counter(a).values()
b = 0
for i in count:
    b = b + i * (i-1)
b=int(b/2)
print(b)
### BUGGY CODE ###

n, m = map(int, input().split())
d = dict()
for _ in range(n):
    a, b = map(int, input().split())
    d.setdefault(a, [])
    d[a].append(b)

l = []
ans = 0
for i in range(1, m + 1):
    if i in d:
        l += d[i]
        l.sort()
    if len(l) > 0:
        m = l.pop()
        ans += m
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop

n, m = map(int, input().split())
d = dict()
for _ in range(n):
    a, b = map(int, input().split())
    d.setdefault(a, [])
    d[a].append(-b)

h = []
ans = 0
for i in range(1, m + 1):
    for b in d.get(i, []):
        heappush(h, b)
    if len(h) > 0:
        m = heappop(h)
        ans -= m
print(ans)
### BUGGY CODE ###

import collections
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
AB_C=[0 for i in range(N-1)]
D=collections.Counter([i[0] for i in AB]+[i[1] for i in AB]).most_common()
M=D[0][1]
print(M)




data=[set() for i in range(N+1)]
idxdata=set([i for i in range(N-1)])
d=0
while idxdata or d<=2:
    #print(idxdata)
    count_c=1
    delidx=set()
    for i in idxdata:
        a,b=AB[i]
        if a==D[d][0] or b==D[d][0]:
            while not(count_c not in data[a] and count_c not in data[b]):
                count_c+=1
            AB_C[i]=count_c
            data[a].add(count_c)
            data[b].add(count_c)
            delidx.add(i)
    d+=1
    idxdata=idxdata-delidx




for i in idxdata:
    a,b=AB[i]
    #print(a,b,"a,b")
    for m in range(1,M+1):
        if m not in data[a] and m not in data[b]:
            data[a].add(m)
            data[b].add(m)
            print(m)
            break


for i in AB_C:
    print(i)


### FIXED CODE ###

from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]

for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=deque([1])
delset=set()
while stack:
    #print(C)
    #print(Cpath,"Cpath")
    a=stack[0]
    count=1
    for b in P[a]:
        #b=P[a][-1]
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        stack.append(b)
        #P[a].remove(b)
        P[b].remove(a)
    P[a].clear()
    stack.popleft()

print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])
### BUGGY CODE ###

N,M = list(map(int,input().split()))
A = []
B = []
ans = 0
for _ in range(N):
    i = list(map(int,input().split()))
    A.append(i[0])
    B.append(i[1])
while M != 0:
    ans += min(A)
    M -= 1
    B[A.index(min(A))] -= 1
    if B[A.index(min(A))] <= 0:
        B.pop(A.index(min(A)))
        A.pop(A.index(min(A)))
print(ans)

### FIXED CODE ###

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

AB = [list(map(int,input().split())) for i in range(N)]
AB.sort()
ans = 0
for _ in range(N):
    if AB[_][1] >= M:
        ans += AB[_][0]*M
        break
    else:
        ans += AB[_][0]*AB[_][1]
        M -= AB[_][1]
print(ans)
### BUGGY CODE ###

import numpy as np
N=int(input())
P=list(map(int,input().split()))

ct=0
for i in range(N):
	if np.min(P[:i+1])==P[i]:
		ct+=1


print(ct)

### FIXED CODE ###

import numpy as np
N=int(input())
P=list(map(int,input().split()))

ct=0
min_p=P[0]
for i in range(N):
	if P[i]<=min_p:
		min_p=P[i]
		ct+=1


print(ct)
### BUGGY CODE ###

h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(map(int, input().split())))
for i in range(h):
    l = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = grid[i][j] - l[j]

unba = []

# 0行目
l = [[grid[0][0], -grid[0][0]]]
for i in range(1, w):
    l1 = [j + grid[0][i] for j in l[i-1]]
    l2 = [j - grid[0][i] for j in l[i-1]]
    l.append(l1 + l2)
unba.append(l)

# 1~h-1行目
for i in range(1, h):

    # i行0列
    l1 = [j + grid[i][0] for j in unba[i-1][0]]
    l2 = [j - grid[i][0] for j in unba[i-1][0]]
    l = [l1 + l2]

    # i行j列
    for j in range(1, w):
        l1 = [k + grid[i][j] for k in l[j-1]]
        l2 = [k - grid[i][j] for k in l[j-1]]
        l3 = [k + grid[i][j] for k in unba[i-1][j]]
        l4 = [k - grid[i][j] for k in unba[i-1][j]]
        l.append(l1 + l2 + l3 + l4)
    unba.append(l)

ans = abs(unba[h-1][w-1][0])
for i in unba[h-1][w-1]:
    if abs(i) < ans:
        ans = abs(i)
print(ans)

### FIXED CODE ###

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        g.append(list(map(int, input().split())))
    for i in range(h):
        k = list(map(int, input().split()))
        for j in range(w):
            g[i][j] = abs(g[i][j] - k[j])

    m = (h + w) * 80

    if m == 0:
        print(0)
        exit()

    dp = [[False] * m for _ in range(w)]
    dp[0][g[0][0]] = True
    for j in range(1, w):
        for k in range(m):
            if dp[j-1][k]:
                dp[j][abs(k - g[0][j])] = True
                dp[j][k + g[0][j]] = True
    
    for i in range(1, h):
        new_dp = [[False] * m for _ in range(w)]
        for k in range(m):
            if dp[0][k]:
                new_dp[0][abs(k - g[i][0])] = True
                new_dp[0][k + g[i][0]] = True
        
        for j in range(1, w):
            for k in range(m):
                if new_dp[j-1][k] or dp[j][k]:
                    new_dp[j][abs(k - g[i][j])] = True
                    new_dp[j][k + g[i][j]] = True
        dp = new_dp

    for j in range(m):
        if dp[w-1][j]:
            print(j)
            break

main()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
d = []
for i, ele in enumerate(a,1):
    d.append( [(i+ele),(i-ele)] )

cnt = 0

for i in range(n):
    for j in range(i+1,n):
        if d[i][0] == d[j][1]:
            cnt += 1

print(cnt)


### FIXED CODE ###

from collections import defaultdict

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

cnt = 0
d = defaultdict(int)

for i in range(n):
    cnt += d[i-a[i]]
    d[i + a[i]] += 1

print(cnt)
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
s = list(set(a))

P = [0] * (10 ** 6 + 1)

for x in s:
    t = x
    while t <= 10**6:
        P[t] += 1
        t += x

ans = 0

for x in a:
    #print(P[x])
    if P[x] == 1 and c[x] == 1:
        ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A_li = list(map(int, input().split()))
s_li = [0]
for i in range(N) :
    s_li.append(s_li[i] + A_li[i])
s_num = set(s_li)
ans = 0
for sn in s_num :
    cnt = s_li.count(sn)
    ans += cnt * (cnt - 1) // 2
print(ans)

### FIXED CODE ###

N = int(input())
A_li = list(map(int, input().split()))
s_li = [0]
for i in range(N) :
    s_li.append(s_li[i] + A_li[i])
s_dic = {}
for s in s_li :
    if s in s_dic :
        s_dic[s] += 1
    else :
        s_dic[s] = 1
ans = 0
for sd in s_dic.values() :
    ans += sd * (sd - 1) // 2
print(ans)
### BUGGY CODE ###

import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
S =sum(A)
cut = []
for k in range(N):
  cut.append(K*A[k]//S)

length = []
for k in range(N):
  length.append([A[k] / (cut[k]+1), k])

length.sort(key = lambda x: x[0], reverse=True)

def nibun_insert(lis, item):
  end = len(lis)
  start = 0
  now = (end+start)//2
  while end > start+1:
    if lis[now][0] > item[0]:
      start = 0 + now
      now = (now + end)//2
    else:
      end = 0 + now
      now = (now + start)//2
  return lis[:now+1] + [item] + lis[now+1:]
  

C = sum(cut)
res = K - C
length = length[:res+1]
for k in range(res):
  cut[length[0][1]] += 1
  length[0][0] = length[0][0]*cut[length[0][1]]/(cut[length[0][1]]+1)
  if length[0][0] < length[1][0]:
    length = nibun_insert(length[1:], length[0])

   
print(math.ceil(length[0][0]))


### FIXED CODE ###

import math
from collections import deque
N, K = map(int, input().split())
A = list(map(int, input().split()))
S =sum(A)
cut = []
for k in range(N):
  cut.append(K*A[k]//S)

length = []
for k in range(N):
  length.append([A[k] / (cut[k]+1), k])

length.sort(key = lambda x: x[0], reverse=True)

def nibun_insert(lis, item):
  end = len(lis)
  start = 0
  now = (end+start)//2
  while end > start+1:
    if lis[now][0] > item[0]:
      start = 0 + now
      now = (now + end)//2
    else:
      end = 0 + now
      now = (now + start)//2
  return deque(lis[:now+1] + [item] + lis[now+1:])
  

C = sum(cut)
res = min(K - C, N)
length = length[:res+1]
length = deque(length)
for k in range(res):
  a = length.popleft()
  cut[a[1]] += 1
  a[0] = a[0]*cut[a[1]]/(cut[a[1]]+1)
  if a[0] <= length[-1][0]:
    length.append(a)
  elif a[0] >= length[0][0]:
    length.appendleft(a)
  else:
    length = nibun_insert(list(length), list(a))
  length.pop()

print(math.ceil(length.popleft()[0]))
### BUGGY CODE ###

S = input()

mod = [0] * (2019+1)

tmp = ""
for i in range(1, len(S)+1):
    tmp = int(S[-i] + str(tmp))
    mod[tmp % 2019] += 1

ans = mod[0]

for i in range(1, 2020):
    if mod[i] >= 2:
        ans += (mod[i] * (mod[i]-1)) // 2
print(ans)

### FIXED CODE ###

S = input()

n_i_to_j_mod = [0] * (2019+1) # 2019で割った余りがiになるようなSの部分連続文字列の個数
i_to_end_mod = [0] * (len(S)+1) # S[-i:](Sの後方i文字)を2019で割ったときの余り

for i in range(1, len(S)+1):
    if i == 1:
        i_to_end_mod[1] = int(S[-1]) % 2019
    else:
        i_to_end_mod[i] = (i_to_end_mod[i-1] + int(S[-i]) * pow(10, i-1, 2019)) % 2019
    n_i_to_j_mod[i_to_end_mod[i]] += 1

ans = n_i_to_j_mod[0] + (n_i_to_j_mod[0] * (n_i_to_j_mod[0]-1))//2
for i in range(1, 2019):
    if n_i_to_j_mod[i] >= 2:
        ans += (n_i_to_j_mod[i] * (n_i_to_j_mod[i]-1)) // 2
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
ans = 1
l = list(map(int,input().split()))
if l.count(0) != 0 :
    print(0)
    exit()
for i in range(n) :
    ans *= l[i]
    if ans > 10**18 :
        print('-1')
        exit()
print(ans)
### BUGGY CODE ###

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

cities_prefec = {}
data = []
cities = []
years = []

for i in range(M):
    prefec_id, year = map(int, input().split())

    data.append(
        {
            "pref_id": prefec_id,
            "year": year
        }
    )

    if prefec_id in cities_prefec:
        bisect.insort(cities_prefec[prefec_id], year)
    else:
        cities_prefec[prefec_id] = [year]


for d in data:
    p_id = d["pref_id"]
    cn = bisect.bisect_left(cities_prefec[p_id], d["year"]) + 1
    print("{0:0>6}{1:0>6}".format(p_id, cn))


### FIXED CODE ###

if __name__ == "__main__":
    _, M = map(int, input().split())
    
    outputs = [0 for _ in range(M)]
    cities = {}

    for i in range(M):
        pref, year = map(int, input().split())
        
        if pref not in cities:
            cities[pref] = {}

        cities[pref][year] = i

    for p in cities:
        city_years = list(cities[p].keys())
        city_years.sort()

        for i, cy in enumerate(city_years):
            outputs[cities[p][cy]] = "{:06}{:06}".format(p, i + 1)

    for line in outputs:
        print(line)
### BUGGY CODE ###

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

for i in range(m):
    a[-1] = a[-1] // 2
    a.sort()

print(sum(a))

### FIXED CODE ###

import heapq


def neg_int(a):
    return -1 * int(a)


n, m = map(int, input().split())
a = sorted(list(map(neg_int, input().split())))
heapq.heapify(a)

for i in range(m):
    value = -1 * ((-1 * heapq.heappop(a)) // 2)
    heapq.heappush(a, value)

print(sum(a) * -1)
### BUGGY CODE ###

"""
dp的な発想で解けるかな？
下の桁から見る。桁を一つずつ
"""
from collections import defaultdict
S = input()
N = len(S)
S = S[::-1]

ans = 0
memo = defaultdict(int)
num = 0
memo[0] = 1
for i in range(N):
    num += pow(10,i)*int(S[i])
    r = num%2019
    ans += memo[r]
    memo[r] += 1

print(ans)

### FIXED CODE ###

"""
dp的な発想で解けるかな？
下の桁から見る。桁を一つずつ
"""
from collections import defaultdict
S = input()
N = len(S)
S = S[::-1]

ans = 0
memo = defaultdict(int)
num = 0
memo[0] = 1
for i in range(N):
    num = (num+(pow(10,i,2019)*int(S[i]))%2019)%2019
    ans += memo[num]
    memo[num] += 1

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

a, b, x = map(int, input().split())

cnt = 0
# a以上b以下の数字
for i in range(a,b+1):
    # 割り切れる数を数える
    if i%x==0:
        cnt+=1
        
print(cnt)

### FIXED CODE ###

from decimal import Decimal
a, b, x = map(int, input().split())

print(b//x-(a-1)//x)
### BUGGY CODE ###

import sys
import itertools
import collections

input = sys.stdin.readline

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for _ in range(q):
        n, x, m = map(int, input().split())
        dmodm = [y%m for y in d]
        dmodmCounter = collections.Counter(dmodm)
        dmodmkCounter = collections.Counter(dmodm[:((n-1)%k)])
        dmodcum = [0] + list(itertools.accumulate(dmodm))
        p0 = dmodmCounter[0] * ((n-1)//k) + dmodmkCounter[0]
        an = x + dmodcum[-1] * ((n-1)//k) + dmodcum[(n-1)%k]
        p1 = an//m - x//m
        ans = n - (p0 + p1) - 1
        print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import itertools
import collections

input = sys.stdin.readline

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    for _ in range(q):
        n, x, m = map(int, input().split())
        dmodm = [y%m for y in d]
        kmod = (n-1)%k
        kdiv = (n-1)//k
        cnt = 0; cntm = 0
        for i in range(k):
            cnt += dmodm[i] == 0
            cntm += (dmodm[i] == 0 and i < kmod)
        #dmodmCounter = collections.Counter(dmodm)
        #dmodmkCounter = collections.Counter(dmodm[:kmod])
        dmodcum = list(itertools.accumulate(dmodm))
        #p0 = dmodmCounter[0] * kdiv + dmodmkCounter[0]
        p0 = cnt * kdiv + cntm
        an = x + (kmod != 0) * dmodcum[kmod-1] + dmodcum.pop() * kdiv
        p1 = an//m - x//m
        ans = n - (p0 + p1) - 1
        print(ans)

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

from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
import bisect
#=================================================#
n=int(int(input()))
A=INPUT()
A.sort()
i=0
j=i+1
ans=0
while(i<n-2):
    k=j+1
    while(k<n and A[k]<(A[i]+A[j])):
        k+=1
    ans+=k-j-1
    j+=1
    if j>=n:
        i+=1
        j=i+1
print(ans)


### FIXED CODE ###

from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
import math
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math as M
MOD=10**9+7
import bisect
#####################################
n=int(input())
A=INPUT()
A.sort()
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=bisect.bisect_left(A,A[i]+A[j],0,n)-1-j
print(ans)
### BUGGY CODE ###

S = raw_input()
Q = int(raw_input())

is_reversed = False

for i in range(Q):
    query = raw_input().split()
    if query[0] == "1":
        is_reversed = not is_reversed
    elif query[0] == "2":
        F = int(query[1])
        C = query[2]
        if F == 1:
            if not is_reversed:
                S = C + S
            else:
                S = S + C
        elif F == 2:
            if not is_reversed:
                S = S + C
            else:
                S = C + S


if not is_reversed:
    ans =  S
else:
    ans = S[::-1]
print ans


### FIXED CODE ###

def main():
    S = raw_input()
    Q = int(raw_input())

    is_reversed = False
    sentou = []
    owari = []

    for _ in range(Q):
        query = raw_input().split()
        if query[0] == "1":
            is_reversed = not is_reversed
        elif query[0] == "2":
            F = query[1]
            C = query[2]
            if F == "1":
                if not is_reversed:
                    sentou.append(C)
                else:
                    owari.append(C)
            elif F == "2":
                if not is_reversed:
                    owari.append(C)
                else:
                    sentou.append(C)

    S = "".join(sentou[::-1]+list(S)+owari)


    if not is_reversed:
        print S
    else:
        print S[::-1]

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

N = int(input())
ans = 0

for i in range(N):
    ans += i

print(ans)


### FIXED CODE ###

N = int(input())
print(N * (N-1) // 2)
### BUGGY CODE ###

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

dp = [float('inf')] * N
dp[0] = 0
for i in range(1,len(A)):
    jmp = min(i,K)
    # for j in range(1,jmp+1):
        # dp[i] = min(dp[i], dp[i-j]+abs(A[i]-A[i-j]))
    dp[i] = min([dp[i-j]+abs(A[i]-A[i-j]) for j in range(1, jmp+1)])
            
print(dp[N-1])

### FIXED CODE ###

def main():
    N,K=map(int, input().split())
    A = list(map(int, input().split()))

    dp = [float('inf')] * N
    dp[0] = 0
    for i in range(1,len(A)):
        jmp = max(0,i-K)
        dp[i] = min([dp[j]+abs(A[i]-A[j]) for j in range(jmp, i)])
    print(dp[N-1])

main()