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

# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self, size):
        list.__init__(self)
        self.size = size
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle(N2)
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        cnt = 0
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            cnt += 1
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if tx < 0 or ty < 0 or tx >= N or ty >= N:
                    continue
                v = copy.copy(u)
                v[u.space], v[tx * N + ty] = v[tx * N + ty], v[u.space]
                v.space = tx * N + ty
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))





### FIXED CODE ###

# -*- coding: utf-8 -*-

from collections import deque
import copy

class Puzzle(list):
    def __init__(self):
        list.__init__(self)
        self.space = None
        self.path = ""
    
    def __hash__(self):
        return hash(str(self[:]))

if __name__ == '__main__':
    
    N = 3
    N2 = 9
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    d = ["u", "l", "d", "r"]

    p = Puzzle()
    for i in range(N):
        p += [int(x) for x in input().split()]
    for i in range(N2):
        if p[i] == 0:
            p[i] = N2
            p.space = i
    target = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    def isTarget(p):
        return p[:] == target[:]

    def bfs(s):
        Q = deque()
        V = set()
        Q.append(s)
        V.add(s)
        while Q:
            u = Q.popleft()
            if isTarget(u):
                return u.path
            sx = u.space // N
            sy = u.space % N
            for r in range(4):
                tx = sx + dx[r]
                ty = sy + dy[r]
                if not (0<= tx < N and 0 <= ty < N):
                    continue
                v = Puzzle()
                v[:] = u[:]
                v.path = u.path
                change = tx * N + ty
                v[u.space], v[change] = v[change], v[u.space]
                v.space = change
                if not v in V:
                    V.add(v)
                    v.path += d[r]
                    Q.append(v)

        return "unsolvable"

    ans = bfs(p)
    print(len(ans))
### BUGGY CODE ###

from fractions import *
n,*a=map(int,open(0).read().split())
mod=10**9+7
b=a[0]
for i in a:
    b=b*i//gcd(b,i)
print(sum(b//i%mod for i in a)%mod) 

### FIXED CODE ###

from fractions import *
n,*a=map(int,open(0).read().split())
b=1
for i in a:b*=i//gcd(b,i)
print(sum(b//i for i in a)%(10**9+7))
### BUGGY CODE ###

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

ls = []
ans = 0

for i in range(k):
    ans += p[i]
    
ls.append([ans,0])

for i in range(n-k):
    ans -= p[i]
    ans += p[i+k]
    ls.append([ans,i+1])
    

ls = sorted(ls,reverse=True)

ans = 0
for i in range(k):
    for j in range(p[ls[0][1]+i]):
        ans += (1/p[ls[0][1]+i]*(j+1))
    
print(ans)
        

### FIXED CODE ###

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

ls = []
ans = 0

for i in range(k):
    ans += p[i]
    
max_ans = ans
max_index = 0

for i in range(n-k):
    ans -= p[i]
    ans += p[i+k]
    if max_ans < ans:
        max_ans = ans
        max_index = i+1

ans = 0
for i in range(k):
    pp = p[max_index+i]
    for j in range(pp):
        ans += (1/pp*(j+1))
    
print(ans)
### BUGGY CODE ###

n = int(input())
if n==1:
    print(0)
else:
    print(sum([i for i in range(n)]))

### FIXED CODE ###

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

N,K=(int(x) for x in input().split())
P=list(map(int, input().split()))
S=0
for i in range(N):
    s=sum(P[i:i+K])
    S=max(S,s)
print((S+K)/2)

### FIXED CODE ###

N,K=(int(x) for x in input().split())
P=list(map(int, input().split()))
s=sum(P[0:K])
ans=[s]

for i in range(K,N):
    s=s+P[i]-P[i-K]
    ans.append(s)

S=max(ans)
print((S+K)/2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def input_converter(key_string):
    key_string = key_string.replace('A', '1')
    key_string = key_string.replace('T', '2')
    key_string = key_string.replace('C', '3')
    key_string = key_string.replace('G', '4')
    return int(key_string)


class HashTable(object):
    def __init__(self, hash_size = 2 ** 15):
        self.hash_size = hash_size
        self.hash_array = [None] * self.hash_size

    def insert_value(self, data, key):
        collision_number = 0
        next_index = self.hash_function(key, collision_number)
        while self.hash_array[next_index] is not None:
            collision_number += 1
            next_index = self.hash_function(key, collision_number)
        # print self.hash_array[next_index]
        self.hash_array[next_index] = data

    def search_value(self, data, key):
        collision_number = 0
        next_index = self.hash_function(key, collision_number)
        while True:
            if (self.hash_array[next_index] is None) or (collision_number > self.hash_size):
                return False
            elif self.hash_array[next_index] == data:
                return True
            else:            
                collision_number +=1
                next_index = self.hash_function(key, collision_number)

    def hash_function(self, key, collision_number):
        def h1(key):
            return key % self.hash_size
    
        def h2(key):
            return key % (self.hash_size - 1)

        return (h1(key) + collision_number * h2(key)) % self.hash_size


def main():
    hash_table = HashTable()
    input_size = int(raw_input())
    counter = 0
    while counter < input_size:
        command, key = raw_input().split(' ')
        if command == 'insert':
            hash_table.insert_value(key, input_converter(key))
        else:
            if hash_table.search_value(key, input_converter(key)):
                print 'yes'
            else:
                print 'no'
        counter += 1


if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

dictionary = {}
input_num = int(raw_input())
counter = 0
while counter < input_num:
    command, key = raw_input().split(' ')
    if command == 'insert':
        dictionary[key] = None
    else:
        if key in dictionary:
            print 'yes'
        else:
            print 'no'

    counter += 1
### BUGGY CODE ###

dates = [int(i) for i in input().split(" ")]
X = dates[0]
K = dates[1]
D = dates[2]

if X >= 0:
    while X > 0 and K > 0:
        X -= D
        K -= 1
else:
    while X <= 0 and K > 0:
        X += D
        K -= 1

if X >= 0:
    if K % 2 == 0:
        print(abs(X))
    else:
        print(abs(X - D))
else:
    if K % 2 == 0:
        print(abs(X))
    else:
        print(abs(X + D))


### FIXED CODE ###

import math

dates = [int(i) for i in input().split(" ")]
X = dates[0]
K = dates[1]
D = dates[2]
numDiv = math.ceil(abs(X) / D)

if numDiv < K:
    if X >= 0:
        X -= numDiv * D
        K -= numDiv
    else:
        X += numDiv * D
        K -= numDiv
else:
    if X >= 0:
        X -= K * D
        K = 0
    else:
        X += K * D
        K = 0

if X >= 0:
    if K % 2 == 0:
        print(abs(X))
    else:
        print(abs(X - D))
else:
    if K % 2 == 0:
        print(abs(X))
    else:
        print(abs(X + D))
### BUGGY CODE ###

n = int(input())
alist = [int(input()) for _ in range(n)]

import copy

alist_copy = copy.copy(alist)
for i, v in enumerate(alist):
    alist_copy.pop(i)
    print(max(alist_copy))
    alist_copy = copy.copy(alist)

### FIXED CODE ###

n = int(input())
alist = [int(input()) for _ in range(n)]

import copy
alist_copy = copy.copy(alist)

alist_copy.sort()
max_value = alist_copy[-1]
next_value = alist_copy[-2]
for a in alist:
    if a == max_value:
        print(next_value)
    else:
        print(max_value)
### BUGGY CODE ###


import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

N, M, K = map(int, input().rstrip().split(' '))

comb = cmb(N*M-2, K-2)

cost = 0
for d in range(1, N):
    cost += d * M**2 * (N - d) * comb
    cost %= 1000000007
for d in range(1, M):
    cost += d * N**2 * (M - d) * comb
    cost %= 1000000007
    
print(cost)



### FIXED CODE ###


import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

N, M, K = map(int, input().rstrip().split(' '))

comb = cmb(N*M-2, K-2) % 1000000007

cost = 0
for d in range(1, N):
    cost += d * M**2 * (N - d) * comb
    cost %= 1000000007
for d in range(1, M):
    cost += d * N**2 * (M - d) * comb
    cost %= 1000000007
    
print(cost)
### BUGGY CODE ###

# 小さいのを2つ選んで最後の1つをにぶたん
n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        ok, ng = j, n
        while (ng - ok) > 1:
            mid = (ng + ok) // 2
            if l[i] + l[j] > l[mid]:
                ok = mid
            else:
                ng = mid
        ans += ok - j
print(ans)


### FIXED CODE ###

# ソートしたやつの小さい方から2つを決めてもうひとつはにぶたん
# 3, 5としたときに残りの一つは5, 6, 7みたいになる
# このにぶたんなんか実装がめっっっちゃむずくない？サンプル1が通らんのだが
# やったけどTLEなるな

import bisect

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


def lower_bound(arr, x):
    l, r = 0, len(arr)
    while l < r:
        mid = (l + r) // 2
        if arr[mid] < x:
            l = mid + 1
        else:
            r = mid
    return l


ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        idx_l = lower_bound(arr, arr[i] + arr[j]) - 1
        # print(
        #     "arr[{}]+arr[{}]={}より小さくなるはじめてのインデックス {}".format(
        #         i, j, arr[i] + arr[j], idx_l
        #     )
        # )
        # print("idx_l = {}, arr[{}]={}".format(idx_l, idx_l, arr[idx_l]))
        # print("範囲 {}".format(arr[j + 1 : idx_l + 1]))
        ans += len(arr[j + 1 : idx_l + 1])
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, K: int, x: "List[int]"):
    x = np.array(x)
    score = 10**9
    x_s = sorted(x[x < 0], reverse=True)
    x_len_plus = len(x[x >= 0])
    x_len_minus = len(x[x < 0])
    for right in range(min(K + 1, x_len_plus + 1)):
        left = min(K - right, max(0, x_len_minus))
        if right + left == K:
            rpath = 0
            lpath = 0
            if x_len_plus > 0:
                rpath = x[x >= 0][right - 1]
            if x_len_minus > 0:
                lpath = abs(x_s[left - 1])
            score = min(score, rpath + lpath + min(rpath, lpath))

    print(score)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, K = map(int, input().split())
    x = list(map(int, input().split()))
    solve(N, K, x)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, K: int, x: "List[int]"):
    x = np.array(x)
    score = 10**9
    x_s = sorted(x[x < 0], reverse=True)
    x_plus = x[x >= 0]
    x_len_plus = len(x_plus)
    x_len_minus = len(x_s)
    for right in range(min(K + 1, x_len_plus + 1)):
        left = min(K - right, x_len_minus)
        if right + left == K:
            if x_len_plus > 0:
                rpath = x_plus[right - 1]
            else:
                rpath = 0
            if x_len_minus > 0:
                lpath = abs(x_s[left - 1])
            else:
                lpath = 0
            score = min(score, rpath + lpath + min(rpath, lpath))

    print(score)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, K = map(int, input().split())
    x = list(map(int, input().split()))
    solve(N, K, x)

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

import bisect


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

for _ in range(m):
    a_tmp = a.pop()
    a_tmp //= 2
    if(len(a)==0):a.append(a_tmp)
    else:
        if(a_tmp >= a[-1]):a.append(a_tmp)
        elif(a_tmp <= a[0]):a.insert(0,a_tmp)
        else:
            index = bisect.bisect_left(a,a_tmp)
            a.insert(index,a_tmp)


print(sum(a))


### FIXED CODE ###

import heapq

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

heapq.heapify(a)

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

import sys
input = sys.stdin.buffer.readline
from heapq import *

h, w = map(int, input().split())
grid = [None for _ in range(h)]
poss = [[set() for x in range(w)] for y in range(h)]
tmp = [map(int, input().split()) for _ in range(h * 2)]
for i, (l1, l2) in enumerate(zip(tmp, tmp[h:])):
	grid[i] = [abs(x - y) for x, y in zip(l1, l2)]
q = [(0, 0)]
poss[0][0].add(-grid[0][0])
poss[0][0].add(grid[0][0])
while q:
	cx, cy = heappop(q)
	for dx, dy in ((1, 0), (0, 1)):
		nx = cx + dx
		ny = cy + dy
		if not (0 <= nx <= w - 1 and 0 <= ny <= h - 1):
			continue
		m = grid[ny][nx]
		for c in poss[cy][cx]:
			poss[ny][nx].add(c - m)
			poss[ny][nx].add(c + m)
		heappush(q, (nx, ny))
print(min(abs(x) for x in poss[-1][-1]))


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

h, w = map(int, input().split())
a = [map(int, input().split()) for _ in range(h)]
b = [map(int, input().split()) for _ in range(h)]
g = [list(abs(x - y) for x, y in zip(l1, l2)) for l1, l2 in zip(a, b)]
poss = [[0] * w for _ in range(h)]
poss[0][0] |= 1 << 6400 + g[0][0]
poss[0][0] |= 1 << 6400 - g[0][0]
for i in range(h):
	for j in range(w - 1):
		poss[i][j + 1] |= poss[i][j] << g[i][j + 1]
		poss[i][j + 1] |= poss[i][j] >> g[i][j + 1]
	if i != h - 1:
		for j in range(w):
			poss[i + 1][j] |= poss[i][j] << g[i + 1][j]
			poss[i + 1][j] |= poss[i][j] >> g[i + 1][j]
res = poss[-1][-1]
for i in range(6400):
	if res & (1 << 6400 + i) or res & (1 << 6400 - i):
		print(i)
		exit()
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    v = a[i]
    a[i] = 0
    ans = max(a)
    print(ans)
    a[i] = v

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(a,reverse=True)
for i in range(n):
    if b[0] == a[i]:
        ans = b[1]
    else:
        ans = b[0]
    print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
l = []
ans = []
for i in range(q):
    l1 = [int(i) for i in input().split()]
    l.append(l1)
#ここまで入力
for i in l:
    count = 0
    s_1 = s[i[0]-1:i[1]]
    for i in range(len(s_1)-1):
        if s_1[i]=="A":
            if s_1[i+1]=="C":
                count += 1
    ans.append(count)
#ここから出力
for i in ans:
    print(i)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
ac = [0 for i in range(n+1)]
ans = []
for i in range(len(s)-1):
    if s[i:i+2]=="AC":
        ac[i+1] = ac[i] + 1
    else:
        ac[i+1] = ac[i]

for i in range(q):
    l,r = map(int,input().split())
    print(ac[r-1]-ac[l-1])
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for i in range(M)]
for b, c in BC:
    A.extend([c]*b)
print(sum(sorted(A)[-N:]))

### FIXED CODE ###

from collections import defaultdict as dd
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [tuple(map(int, input().split())) for i in range(M)]

cards = dd(int)
for a in A:
    cards[a] += 1
for b, c in BC:
    cards[c] += b

ans = 0
for k, v in sorted(cards.items(), key=lambda x: -x[0]):
    if N > v:
        ans += k*v
    else:
        ans += k*N
        break
    N -= v
print(ans)
### BUGGY CODE ###

n = int(raw_input())
ls = []
for i in range(n):
    inp = raw_input()
    if inp[0] == "i":
        ls.append(inp[7:])
    else:
        print "yes" if inp[5:] in ls else "no"
            

### FIXED CODE ###

n = int(raw_input())
ls = {}
for i in range(n):
    inp = raw_input()
    if inp[0] == "i":
        ls[inp[7:]] = 1
    else:
        try:
        	if ls[inp[5:]]: print "yes"
        except:
        	print "no"
### BUGGY CODE ###

a, b, n = map(int, input().split())
def func(i, j, k):
    return (i*k)//j - i*(k//j)
ans = 0
for i in range(1, min(b+1, n+1)):
    if func(a, b, i) > ans:
        ans = func(a, b, i)
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
def func(i, j, k):
    return (i*k)//j - i*(k//j)
m = min(n, b-1)
r = (a*min(n, b-1)) // b
while ((a*m) // b) == r:
    m -= 1
print(func(a, b, m+1))
### BUGGY CODE ###

n = input()
l = len(n)
mod = [0]*2019
mod[0] += 1

for i in range(l):
  a = int(n[i:]) % 2019
  mod[a] += 1

res = 0  
for m in mod:
  res += m*(m-1)/2
print(int(res))


### FIXED CODE ###

n = input()
mod = [0]*2019
mod[0] += 1
T = 0
d = 1 # 桁数
for i, s in enumerate(n[::-1]):
  T += int(s) * d
  T %= 2019
  d = (d * 10) % 2019
  mod[T] += 1
  
res = 0  
for m in mod:
  res += m*(m-1)/2
print(int(res))
### BUGGY CODE ###

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

def how_two(n):
    a = 0
    while n %2 ==0:
        a+=1
        n//=2
    return a

log2 = how_two(A[0])
for i in A:
    tmplog2 = how_two(i)
    if log2!=tmplog2:
        log2 =0
        break
        
        
if log2==0:
    print(0)
else:
    def p_prime(n): 
        prime = [2]
        for i in range(3,n+1):
            flag = 0
            for j in prime:
                if i%j == 0:
                    flag = 1
                    break
                if i**0.5 < j:
                    break
            if flag == 0:
                prime.append(i)
        return prime

    mod = 10**9+7
    prime = p_prime(int(mod**0.5+1))
    def soinsuu(M):
        a = {}
        for p in prime:
            count = 0
            while M%p ==0:
                count += 1
                M //= p
            if count > 0:
                a[p] = count
        if M != 1:
            a[M] = 1
        return a

    def LCM(A):
        from collections import defaultdict
        AA = defaultdict(int)
    
        for i in range(len(A)):
            tmp = soinsuu(A[i])
            for j in tmp:
                AA[j] = max(AA[j], tmp[j])
                
        L = 1
        for i in AA:
            L *= pow(i,AA[i])
        return L

    l = LCM(A)
    l //= 2
    ans =(M+l)//(2*l)
    
    print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
AA = max(A)
 
def how_two(n):
    a = 0
    while n %2 ==0:
        a+=1
        n//=2
    return a
 
log2 = how_two(A[0])
for i in A:
    tmplog2 = how_two(i)
    if log2!=tmplog2:
        log2 =0
        break
        
        
if log2==0:
    print(0)
else:
    from fractions import gcd
    l = 1
    dame = 0
    for i in A:
        l = (l*i)//gcd(l,i)
        if l//2 >= 10**9:
            dame = 1
            break
    l //= 2
    
    MAX = (M+l)//(2*l)
    MIN = max(1,-(-(AA+2*l)//(4*l)))
    ans = MAX-MIN +1
    #print(MIN)
    
    if dame==1:
        print(0)
    else:
        print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 26 22:28:26 2020

@author: Kanaru Sato
"""

s = input()
n = len(s)
s = int(s)
dic = {}
mod = 2019

for i in range(1,n+1):
    num = (s%(10**(i)))%mod
    if num in dic:
        dic[num] += 1
    if num not in dic:
        dic[num] = 1

summation = 0
for factor in dic:
    if factor != 0:
        summation += dic[factor]

if 0 in dic:
    ans = summation-(len(dic)-1)+dic[0]
elif 0 not in dic:
    ans = summation-(len(dic))

print(ans)

### FIXED CODE ###

s = list(map(int, list(input())))
n = len(s)

countdic = {}
mod = 2019

num = 0
d = 1
for i in range(1,n+1):
    num += s[n-i]*d
    num %= mod
    if num in countdic:
        countdic[num] += 1
    if num not in countdic:
        countdic[num] = 1
    d = (10*d)%mod

ans = 0
for key in countdic:
    ans += countdic[key]*(countdic[key]-1)//2

if 0 in countdic:
    ans += countdic[0]

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

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

def check(m):
    sm = 0
    for i, a in enumerate(A):
        sm += abs(a - (m+i+1))
    return sm

# 三分探索
low = -INF
hi = INF
while low+2 < hi:
    m1 = (low*2+hi) // 3
    m2 = (low+hi*2) // 3
    res1 = check(m1)
    res2 = check(m2)
    # 今回は下に凸な関数なので値の小さい方に向かって狭めていく
    if res1 <= res2:
        hi = m2
    else:
        low = m1

ans = INF
for i in range(low, low+2):
    ans = min(ans, check(i))
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

# Ai - i の各値を用意してソートする
BN = [AN[i] - (i + 1) for i in range(N)]
BN.sort()
# 中央値を取る
b = BN[len(BN) // 2]
# 最適な b で実際の計算をする
ans = 0
for i in range(N):
    ans += abs(AN[i] - (b + i + 1))
print(ans)