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

from collections import defaultdict


s = input()
n = len(s)

dd = defaultdict(int)

d = [0] * 2019
d[0] = 1
tmp = 0
_10 = 1
# print(s, n)
for i in range(n - 1, -1, -1):
    # print(i, s[i])
    tmp = tmp + int(s[i]) * _10
    _10 *= 10
    # print(tmp, tmp % 2019)
    d[tmp % 2019] += 1


# count = 0
# for i in range(len(d)):
#     if d[i] >= 2:
#         count += (d[i])*(d[i]-1)//2
# print(count)

# # print(dd)
print(sum(v*(v-1)//2 for v in d))


### FIXED CODE ###

import math
s = input()
n = len(s)
count = 0
a = [0 for i in range(2019)]
a[0] = 1
k = 0
b = [0 for i in range(n)]
b[0] = 1
for i in range(1, n):
    b[i] = b[i-1]*10 % 2019

#print(b)
for i in reversed(range(0, n)):
 #   print((b[n-i-1])*int(s[i]) % 2019)
    k += (b[n-i-1])*int(s[i]) % 2019
  #  print(k, k % 2019)
    a[k % 2019] += 1

for i in range(len(a)):
    if a[i] >= 2:
        count += (a[i])*(a[i]-1)//2
print(count)
### BUGGY CODE ###

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

### FIXED CODE ###

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

l = input()
mod = 10**9 + 7
r = 0
one = 0

for i in range(0, len(l)):
    if l[i] == "1":
        r = (r + pow(2, one) * pow(3, len(l) - i - 1, mod)) % mod
        one += 1

r = (r + pow(2, one)) % mod

print(r)

### FIXED CODE ###

l = input()
mod = 10**9 + 7
r = 0
one = 0

for i in range(0, len(l)):
    if l[i] == "1":
        r = (r + pow(2, one, mod) * pow(3, len(l) - i - 1, mod)) % mod
        one += 1

r = (r + pow(2, one, mod)) % mod

print(r)
### BUGGY CODE ###

n,a,b=map(int,input().split())
p=n//(a+b)
if n%(a+b)==0:
	r=0
elif n%(a+b)>=a:
	r=a
else:
	for i in range(a):
		if n%(a+b)==i:
			r=i
ans=p*a+r
print(ans)

### FIXED CODE ###

n,a,b=map(int,input().split())
p=n//(a+b)
if n%(a+b)==0:
	r=0
elif n%(a+b)>=a:
	r=a
else:
	r=n%(a+b)
ans=p*a+r
print(ans)
### BUGGY CODE ###

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline

def main():
    n=int(input())
    d=defaultdict(deque)
    for i in range(n):
        d[i+1]=deque(map(int,input().split()))

    c=0
    while any(d.values()):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip.copy():
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1
                        
        if not f:
            print(-1)
            exit()

    print(c)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import* #defaultdict Counter deque appendleft
import sys
input=sys.stdin.readline
import time
t=time.time()

def main():
    n=int(input())
    d=[[]]+[deque(map(int,input().split()))for i in n*[0]]

    c=0
    while any(d):
        c+=1
        f=0
        skip=set()
        for i in range(1,n+1):
            if i not in skip:
                if d[i]:
                    if d[i][0] in skip:
                        continue
                    elif i==d[d[i][0]][0]:
                        oppo=d[i].popleft()
                        d[oppo].popleft()
                        skip.add(oppo)
                        skip.add(i)
                        f=1

        if not f:
            print(-1)
            exit()
        if abs(time.time()-t)>1:
            print(n*(n-1)//2)
            exit()

    print(c)

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

n = int(input())
list = []
for i in range(n):
    s = str(input())
    if s not in list:
        list.append(s)
print(len(list))

### FIXED CODE ###

import collections

n = int(input())
list = []
for i in range(n):
    s = str(input())
    list.append(s)
c = collections.Counter(list)
print(len(c))
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

K, S = map(int, readline().split())

ans = 0
for X in range(0, K + 1):
    for Y in range(0, K + 1):
        for Z  in range(0, K + 1):
            if X + Y + Z == S:
                ans += 1
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

K, S = map(int, readline().split())

ans = 0
for X in range(0, K + 1):
    for Y in range(0, K + 1):
        Z = S - X - Y
        if 0 <= Z and Z <= K:
            ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
As = sorted(map(int, input().split()))

used = [False] * N

ans = 0
for i in range(31, 0, -1):
    power_of_two = 1 << i
    l = 0
    r = N - 1
    while True:
        while l < N and used[l]:
            l += 1
        while r >= 0 and used[r]:
            r -= 1
        if l >= r:
            break

        if As[l] + As[r] == power_of_two:
            used[l] = True
            used[r] = True
            l += 1
            r -= 1
            ans += 1
        elif As[l] + As[r] < power_of_two:
            l += 1
        else:
            r -= 1

print(ans)



### FIXED CODE ###

N = int(input())
As = sorted(map(int, input().split()))

used = [False] * N

ans = 0
for i in range(31, 0, -1):
    power_of_two = 1 << i
    l = 0
    r = N - 1
    while True:
        while l < N and used[l]:
            l += 1
        while r >= 0 and used[r]:
            r -= 1
        if l >= r:
            break

        if As[l] + As[r] == power_of_two:
            used[l] = True
            used[r] = True
            l += 1
            r -= 1
            ans += 1
        elif As[l] + As[r] < power_of_two:
            l += 1
        else:
            r -= 1

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

n,c=[int(i) for i in input().split()]
x=[[0 for i in range(2)] for j in range(n)]
for i in range(n):
    x[i]= [int(i) for i in input().split()]
x.sort(key=lambda x:x[0])

state=0

left_wa=[0 for i in range(n)]
right_wa=[0 for i in range(n)]


for i in range(n):
    if i==0:
        left_wa[i]=x[i][1]-abs(x[i][0]-state)
    else:
        left_wa[i]=left_wa[i-1]+x[i][1]-abs(x[i][0]-state)
    state=x[i][0]

state=c

for i in range(n):
    if i==0:
        right_wa[i]=x[n-1-i][1]-abs(x[n-1-i][0]-state)
    else:
        right_wa[i]= right_wa[i-1]+x[n-1-i][1]-abs(abs(c-x[n-1-i][0])-abs(state))
    state=c-x[n-1-i][0]

kcal=0

for i in range(n):
    if i!=n-1:
        right=max(right_wa[:n-1-i])-x[i][0]
    else: right=0
    kcal=max(kcal, left_wa[i]+max(0, right))

for i in range(n):
    if i!=n-1:
        left=max(left_wa[:n-1-i])-abs(c-x[n-i-1][0])
    else: left=0
    kcal=max(kcal, right_wa[i]+max(0, left))



#print(left_wa)
#print(right_wa)

print(kcal)

### FIXED CODE ###

n,c=[int(i) for i in input().split()]
x=[[0 for i in range(2)] for j in range(n)]
for i in range(n):
    x[i]= [int(i) for i in input().split()]
x.sort(key=lambda x:x[0])

state=0

left_wa=[0 for i in range(n)]
right_wa=[0 for i in range(n)]

for i in range(n):
    if i==0:
        left_wa[i]=x[i][1]-abs(x[i][0]-state)
    else:
        left_wa[i]=left_wa[i-1]+x[i][1]-abs(x[i][0]-state)
    state=x[i][0]

state=c

for i in range(n):
    if i==0:
        right_wa[i]=x[n-1-i][1]-abs(x[n-1-i][0]-state)
    else:
        right_wa[i]= right_wa[i-1]+x[n-1-i][1]-abs(abs(c-x[n-1-i][0])-abs(state))
    state=c-x[n-1-i][0]

kcal=0

m_right=[0 for i in range(n+1)]
m_left=[0 for i in range(n+1)]

for i in range(n+1):
    if i!=0:
        m_right[i]=max(m_right[i-1], right_wa[i-1])
        m_left[i]=max(m_left[i-1], left_wa[i-1])

#print(m_left)

for i in range(n):
    if i!=n-1:
#        right=max(right_wa[:n-1-i])-x[i][0]
        right= m_right[n-1-i]-x[i][0]
    else: right=0
    kcal=max(kcal, left_wa[i]+max(0, right))

for i in range(n):
    if i!=n-1:
#        left=max(left_wa[:n-1-i])-abs(c-x[n-i-1][0])
       left=m_left[n-1-i]-abs(c-x[n-i-1][0])

    else: left=0
    kcal=max(kcal, right_wa[i]+max(0, left))


print(kcal)
### BUGGY CODE ###

N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a = numX % (popcount_X + 1)
b = numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1): #リストのインデクス，要素，第二引数に開始位置
    if x == '1' and popcount_X == 1:
        print(0); continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - i)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1') #2進数，1の個数
        temp %= p
        ans += 1
    print(ans)

### FIXED CODE ###

N = int(input())
X = input()
popcount_X = X.count('1')
numX = int(X, 2)
a = numX % (popcount_X + 1)
b = numX % (popcount_X - 1) if popcount_X != 1 else 0
for i, x in enumerate(X, 1): #リストのインデクス，要素，第二引数に開始位置
    if x == '1' and popcount_X == 1:
        print(0)
        continue
    ans = 1
    if x == '1':
        temp = (b - pow(2, N - i, popcount_X - 1)) % (popcount_X - 1)
    else:
        temp = (a + pow(2, N - i, popcount_X + 1)) % (popcount_X + 1)
    while temp:
        p = format(temp, 'b').count('1') #2進数，1の個数
        temp %= p
        ans += 1
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
data = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    data[a].append([i,b])  # i本目でbに
    data[b].append([i,a])

k = max(len(data[i]) for i in range(n))
print(k)
ans = [-1 for i in range(n)]


stack = [[0,n,k]]
while stack:
    now,pre,pre_path = stack.pop()
    color = [True for i in range(k + 1)]
    color[ans[pre_path]] = False

    for nex_path, nex in data[now]:
        if nex == pre: continue
        for num, c in enumerate(color):
            if c:
                ans[nex_path] = num
                color[num] = False
                stack.append([nex, now, nex_path])
                break


for x  in ans[:-1]:
    print(x+1)

### FIXED CODE ###

n = int(input())
G = [[] for _ in range(n)]
d = {}
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    d[(a,b)] = d[(b,a)] = i

k = 0
ans = [None]*(n-1)

stack = [(0,-1)] #node, par

while stack:
    now,pre = stack.pop()
    color = 1
    for nex in G[now]:
        if nex == pre:continue
        stack.append((nex,now))
        if pre != -1:
            if color == ans[d[(now,pre)]]:
                color += 1
        ans[d[(now,nex)]] = color
        k = max(k,color)
        color += 1

print(k)
print(*ans, sep="\n")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,m = map(int, raw_input().split())
# 文字列の入力
# 出力
gate = [[0,0]]*m
for i in range(m):
    gate[i]=raw_input().split()

cnt = 0
c = 0
for j in range(n):
    j = j+1
    for i in range(m):
        if j >= int(gate[i][0]) and int(gate[i][1]) >= j:
            c += 1
    if c == m:
        cnt = cnt+1
    c = 0

print cnt

### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m = map(int, raw_input().split())
# 文字列の入力
# 出力
gate = [[0,0]]*m
for i in range(m):
    gate[i]=raw_input().split()

cnt = 0
min_r = n
max_l = 0
for i in range(m):
    g0 = int(gate[i][0])
    g1 = int(gate[i][1])

    if max_l < g0:
        max_l = g0

    if min_r > g1:
        min_r = g1

for j in range(n):
    j=j+1
    if j >= max_l and min_r >= j:
            cnt += 1

print cnt
### BUGGY CODE ###

N = int(input())
goods = []
count = 0
for i in range(N):
  good = str(input())
  if good not in goods:
    goods.append(good)
    count +=1
    
print(count)

### FIXED CODE ###

N = int(input())
goods = {}
count = 0
for i in range(N):
  good = input()
  goods[good] =1
    
    
print(len(goods))
### BUGGY CODE ###

n=int(input())
A=sorted(list(map(int,input().split())),reverse=True)
for a in A:
    if A.count(a)>=2:
        if A.count(a)>=4:
            print(a**2)
            exit()
        else:
            for b in A:
                if b!=a:
                    if A.count(b)>=2:
                        print(a*b)
                        exit()
print(0)

### FIXED CODE ###

from collections import Counter
n=int(input())
A=list(map(int,input().split()))
C=sorted(Counter(A).items(),key=lambda x:x[0],reverse=True)
m=len(C)
for i in range(m):
    if C[i][1]>=4:
        print(C[i][0]**2)
        exit()
    elif C[i][1]>=2:
        a=C[i][0]
        for j in range(i+1,m):
            if C[j][1]>=2:
                print(a*C[j][0])
                exit()
print(0)
### BUGGY CODE ###

n = int(input())
s = input()

max_count = 0
for i in range(n):
    for j in range(n):
        if i >= j:
            continue
        if s[i] == s[j]:
            count = max_count
            while True:
                if i+count <= j and s[i:i+count] == s[j:j+count]:
                    #print(count, i, s[i:i+count])
                    count += 1
                else:
                    max_count = max(max_count, count-1)
                    break
print(max_count)

### FIXED CODE ###

tmp = input()
my_str = input()
 
start = 0
end = 1
max_len = 0
 
while (end < len(my_str)):
    if my_str[start:end] in my_str[end:]:
        if end - start > max_len:
            max_len = end - start
        end += 1
    else:
        start += 1
print(max_len)
### BUGGY CODE ###

import collections
N = int(input())
S = []
for _ in range(N):
    a = str(input())
    S.append(a)
ans = 0
for i in range(N):
    for j in range(i+1, N):
        if sorted(S[i]) == sorted(S[j]):
            ans += 1
print(ans)




### FIXED CODE ###

import collections

N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(s)
ans = 0
for i in set(s):
    n = c[i]
    ans += n * (n - 1) // 2
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    distance = [len(i) for i in order_F]
    x -= distance[0]
    side = []
    vert = []
    sum_s = 0
    sum_v = 0
    s_append = side.append
    v_append = vert.append
    s_append(0)
    v_append(0)
    for i in range(1, len(distance)):
        if i%2 == 0:
            sum_s += distance[i]
            for j in reversed(range(len(side))):
                s_append(side[j] + distance[i])
        else:
            sum_v += distance[i]
            for j in reversed(range(len(vert))):
                v_append(vert[j] + distance[i])
    if  (sum_s - x)/2 in side and (sum_v - y)/2 in vert:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    order_F = []
    order_F = input().rstrip().split('T')
    x, y = map(int, input().split())
    vert_DP = [False] * 8001
    side_DP = [False] * 8001
    vert_DP[0] = True
    side_DP[0] = True
    vert_sum = 0
    side_sum = 0
    distance = [len(order_F[i]) for i in range(len(order_F))]
    order_len = len(order_F)
    x -= len(order_F[0])
    vert_last = 0
    side_last = 0
    for i in range(1, order_len):
        if i % 2 == 0:
            side_sum += distance[i]
            for j in reversed(range(side_last+1)):
                if side_DP[j]:
                    side_DP[j + distance[i]] = True
            side_last += distance[i]
        else:
            vert_sum += distance[i]
            for j in reversed(range(vert_last+1)):
                if vert_DP[j]:
                    vert_DP[j + distance[i]] = True
            vert_last += distance[i]
    if side_sum < x or vert_sum < y:
        print("No")
    elif (side_sum - x) % 2 == 1 or (vert_sum - y) % 2 == 1:
        print("No")
    else:
        if side_DP[(side_sum - x)//2] and vert_DP[(vert_sum - y)//2]:
            print("Yes")
        else:
            print("No")

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

import sys
from collections import deque
from copy import copy

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

max_value = 0

def calc_max_value(V, k, l, r):
    store = deque([])
    for i in range(l):
        if len(V)>0:
            store.append(V.popleft())
            continue
        else:
            break
    for i in range(r):
        if len(V)>0:
            store.append(V.pop())
            continue
        else:
            break
    store = deque(sorted(store))
    for i in range(k-l-r):
        if len(store)>0:
            e = store.popleft()
            if e < 0:
                continue
            else:
                store.appendleft(e)
                break
        else:
            break
    max_value = sum(store)
    return max_value

    
for k in range(K+1):
    for l in range(K+1):
        for r in range(K+1-l):
            max_value = max(max_value, calc_max_value(copy(V), k, l, r))

print(max_value)


### FIXED CODE ###

import sys
from collections import deque
from copy import copy

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

max_value = 0

def calc_max_value(V, K, k, l, r):
    store = deque([])
    for i in range(l):
        if len(V)>0:
            store.append(V.popleft())
            continue
        else:
            break
    for i in range(r):
        if len(V)>0:
            store.append(V.pop())
            continue
        else:
            break
    store = deque(sorted(store))
    for i in range(K-l-r):
        if len(store)>0:
            e = store.popleft()
            if e < 0:
                continue
            else:
                store.appendleft(e)
                break
        else:
            break
    max_value = sum(store)
    return max_value

    
for k in range(min(K+1,N+1)):
    for l in range(k+1):
        for r in range(k+1-l):
            max_value = max(max_value, calc_max_value(copy(V), K, k, l, r))

print(max_value)
### BUGGY CODE ###

n,m = map(int,input().split())
a = []
b = []
ans = 0
for i in range(n):
  aa, bb = map(int,input().split())
  a.append(aa)
  b.append(bb)
ans = 0
mini = 10000000000
while(1):
  for i in range(n):
    if a[i] < mini:
      mini = a[i]
      index = i
  ans = ans + a[index]*min(m,b[index])
  m = m - min(m,b[index])
  if m == 0:
    break
  a.pop(index)
  b.pop(index)
  n = n - 1
  mini = 10000000000
  
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
a = []
b = []
raw = []
ans = 0
for i in range(n):
  raw.append(list(map(int,input().split())))
raw.sort(key=lambda x:x[0])
for i in range(n):
  ans = ans + raw[i][0] * min(raw[i][1],m)
  m = m - min(raw[i][1],m)
  if m == 0:
    break
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from queue import PriorityQueue
 
 

n, m = map(int, input().split())
m_dict = defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    m_dict[a] = m_dict[a] + [b]
    

job_que = PriorityQueue()
    
    
total = 0
for j in range(1, m+1):
    for k in m_dict[j]:
        job_que.put(-k)
 
 
    if job_que:
        total -= job_que.get()
        
    
            
print(total)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
t_r_list = []
for i in range(n):
    t_r_list.append(list(map(int, input().split())))

t_r_list.sort()
que = []
total = 0
l = 0
for j in range(1, m + 1):
    while True:
        if l == n:
            break
        if t_r_list[l][0] != j:
            break
        heapq.heappush(que, -t_r_list[l][1])
        l += 1

    if que:
        total -= heapq.heappop(que)


print(total)
### BUGGY CODE ###

import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    X = il()

    ret = MAX
    for n in range(N - K + 1):
        T = X[n:n + K]
        l = abs(T[0]) + abs(T[0] - T[len(T)-1])
        r = abs(T[len(T)-1]) + abs(T[0] - T[len(T)-1])
        ret = min(ret, l, r)
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    X = il()

    ret = MAX
    for n in range(N - K + 1):
        l = abs(X[n]) + abs(X[n]-X[n+K-1])
        r = abs(X[n+K-1]) + abs(X[n+K-1] - X[n])
        ret = min(ret, l, r)
    print(ret)


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

memo={}
def calc(A, b):
    score = memo.get(b, None)
    if not score is None:
        return score
    score = sum(abs(a-b) for a in A)
    memo[b] = score
    return score

def findmin(A, l, u):
    d = (u-l)//3
    if d == 0:
        return min(calc(A, i) for i in range(l, u+1))
    left, right = l + d, u - d
    sl = calc(A, left) 
    sr = calc(A, right) 
    if sl > sr:
        return findmin(A, left, u)
    else:
        return findmin(A, l, right)

def solve(A):
    A = sorted(a-(i+1) for i, a in enumerate(A))
    return findmin(A, A[0], A[-1])

#solve(list(range(1000, 2*10**5)))
N = int(input())
A = [int(x) for x in input().split()]

#abs(A1-(b+1)) + abs(Ai-(b-i)) + abs(AN-(b-N))


# b1 = A[0]    ならば (A[i]-b1) >= 0
# b2 = A[0] -1 ならば (A[i]-b2) > (A[i]-b1) >= 0 なので、スコアは大きくなる

# b = A[-1] ならば (A[i]-b) <= 0

print(solve(A))



### FIXED CODE ###

memo={}
def calc(A, b):
    score = memo.get(b, None)
    if not score is None:
        return score
    score = sum(abs(a-b) for a in A)
    memo[b] = score
    return score

c = 0
def findmin(A, l, u):
    global c
    c+=1
    d = (u-l)//3
    if d == 0:
        return min(calc(A, i) for i in range(l, u+1))
    left, right = l + d, u - d
    sl = calc(A, left) 
    sr = calc(A, right) 
    if sl > sr:
        return findmin(A, left, u)
    else:
        return findmin(A, l, right)

def solve(A):
    B= [0] * len(A)
    l = A[0]
    u = A[0]
    for i, a in enumerate(A):
        b = a-(i+1)
        l = min(l, b)
        u = max(u, b)
        B[i] = b
    #A = [a-(i+1) for i, a in enumerate(A)]
    return findmin(B, l, u)

N = int(input())
A = [int(x) for x in input().split()]

#abs(A1-(b+1)) + abs(Ai-(b-i)) + abs(AN-(b-N))


# b1 = A[0]    ならば (A[i]-b1) >= 0
# b2 = A[0] -1 ならば (A[i]-b2) > (A[i]-b1) >= 0 なので、スコアは大きくなる

# b = A[-1] ならば (A[i]-b) <= 0
print(solve(A))