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

from collections import deque
N = int(input())
dic = {}
for i in range(N):
  a = [int(i) for i in input().split()]
  dic[i+1] = deque(a)
count = 0
keys = [int(i) for i in dic.keys()]
while True:
  nokori = 0
  flag = True
  log = [-1]*N
  pk = []
  for k in keys:
    if dic[k]==deque([]):
      continue
    p2 = dic[k][0]
#    print(k,p2)
    if log[p2-1]==1:
      continue
    if dic[p2]==deque([]):
      print(-1)
      break
    pk += [k,p2]
    if dic[p2][0]==k and log[k-1]==-1 and log[p2-1]==-1:
      a = dic[k].popleft()
      b = dic[p2].popleft()
#      print('%', a,b)
      log[k-1] = 1
      log[p2-1] = 1
      flag = False
  keys = pk
      
  if keys==[]:
    print(count)
    break
  count += 1
  if flag:
    print(-1)
    break


### FIXED CODE ###

N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

n,m=list(map(int, input().split()))
a=list(map(int, input().split()))
for i in range(m):
	j=a.index(max(a))
	a[j]=a[j]//2
print(sum(a))

### FIXED CODE ###

'''
標準入力
4 4
1 9 3 5
'''

n,m=list(map(int, input().split()))
a=list(map(int, input().split()))
b=[-a[i] for i in range(n)]
#print(b) => [-1, -9, -3, -5]

import heapq
heapq.heapify(b)
#print(b) => [-9, -5, -3, -1]

for i in range(m):
	maximum=heapq.heappop(b)
#forなしでprint(maximum) => -9
	
	maximum=-(-maximum//2)
	heapq.heappush(b,maximum)
print((sum(b))*(-1))
### BUGGY CODE ###

import collections
import math

def comb(n, r):
    if n < 2:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
L = input().split(" ")

c = collections.Counter(L)

d = {}
tmp = 0 

for i in c:
    d[i] = comb(c[i], 2)
    tmp += d[i]
total = tmp

memo = {}
for i in L:
    if i not in memo.keys():
        ans = total - d[i] + comb(c[i]-1, 2)
        memo[i] = ans
        print(ans)
    else:
        print(memo[i])

### FIXED CODE ###

import collections
import math

def comb(n, r):
    if n < 2:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
L = input().split(" ")

c = collections.Counter(L)

d = {}
tmp_total = 0 

memo1 = {}
L2 = {}

for i in c:
    if c[i] not in memo1.keys():
        tmp = comb(c[i], 2)
        memo1[c[i]] = tmp
        tmp_total += tmp
    else:
        tmp_total += memo1[c[i]]
        
total = tmp_total

for i in L:
    ans = total - memo1[c[i]] + memo1[c[i]]*(c[i]-2)//c[i]
    print(ans)
### BUGGY CODE ###

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

def gcd ( ax, ay):
    x = ax
    y = ay
    while (True):
        if x < y :
            tmp = x
            x = y
            y = tmp
        x=x %y
        if x == 0:
            return y
        elif x == 1:
            return 1

def check_pn(num):
    count = 0
    for i in range(2, num):
        if gcd(i, num) != 1:
            return False

    return True


n = int(input())
listdata = []
for i in range(n):
    listdata.append(int(input()))

n=0
for data in listdata:
    n += check_pn(data)

print (n)



### FIXED CODE ###

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

def check_pn(num):
    if (num <2):
        return False
    elif (num==2):
        return True

    if (num%2 == 0):
        return False
    i = 3
    while (i <= num/i):
        if num % i == 0:
            return False
        i += 2

    return True


n = int(input())
listdata = []
for i in range(n):
    listdata.append(int(input()))

n=0
for data in listdata:
    ch = check_pn(data)
    n += ch

print (n)
### BUGGY CODE ###

from itertools import accumulate
N, M, K = map(int,input().split())
A_list = [0] + list(map(int,input().split()))
B_list = [0] + list(map(int,input().split()))
A_sums_list = list(accumulate(A_list))
B_sums_list = list(accumulate(B_list))
for n in range(N + 1):
    if A_sums_list[n] > K:
        break
        A_max = n
for m in range(M + 1):
    if B_sums_list[m] > K:
        break
        B_max = m
ans = 0
for i in range(n + 1):
    for j in range(m + 1):
        if A_sums_list[i] + B_sums_list[j] <= K and i + j > ans:
            ans = i + j
print(ans)

### FIXED CODE ###

import itertools
n, m, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

sa = list(itertools.accumulate(a))
sb = list(itertools.accumulate(b))

output = 0
j = m
for i in range(n + 1):
    if sa[i] > k:
        break
    while sa[i] + sb[j] > k:
        j -= 1
    if output < i + j:
        output = i + j
print(output)
### BUGGY CODE ###

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

def kurikaeshi(x, n, mod):
    if n == 1:
        return x%mod
    elif n %2 == 0:
        return kurikaeshi(x, n//2, mod)**2%mod
    elif n %2 == 1:
        return kurikaeshi(x, n//2, mod)**2*x%mod
    
def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunbo *= a-i
        
    return bunshi*(kurikaeshi(bunbo, mod-2, mod)%mod)
        
        
mod = 1000000007
answer = kurikaeshi(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)

### FIXED CODE ###

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

def kurikaeshi(x, n, mod):
    if n == 1:
        return x%mod
    elif n %2 == 0:
        return kurikaeshi(x, n//2, mod)**2%mod
    elif n %2 == 1:
        return kurikaeshi(x, n//2, mod)**2*x%mod
    
    
def combination(n, a, mod):
    bunbo = 1
    bunshi = 1
    for i in range(a):
        bunshi *= n-i
        bunshi = bunshi%mod
        bunbo *= a-i
        bunbo = bunbo%mod
        
    return bunshi*pow(bunbo, mod-2, mod)%mod
        
        
mod = 1000000007
answer = pow(2, n, mod)
answer -= 1
answer -= combination(n, a, mod)
answer -= combination(n, b, mod)
print(answer%mod)
### BUGGY CODE ###

n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(i1,n):
    for i3 in range(n):
      for i4 in range(i3,n):
        ct=0
        for i5 in range(n):
          if min(x[i1],x[i2])<=l[i5][0]<=max(x[i1],x[i2]) and min(y[i3],y[i4])<=l[i5][1]<=max(y[i3],y[i4]):ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(ans))

### FIXED CODE ###

n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(i1,n):
    for i3 in range(n):
      for i4 in range(i3,n):
        ct=0
        for i5 in range(n):
          if min(x[i1],x[i2])<=l[i5][0]<=max(x[i1],x[i2]) and min(y[i3],y[i4])<=l[i5][1]<=max(y[i3],y[i4]):ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(ans))
### BUGGY CODE ###

n = input()
s = input()

n = int(n)

allnum = set(range(0, 1000))
ans = []

for i in range(n - 2):
    for j in range(i + 1, n - 1):
        for k in range(j + 1, n):
            num = int(s[i]) * 100 + int(s[j]) * 10 + int(s[k])

            if num in allnum and num not in ans:
                ans.append(num)

print(len(ans))

### FIXED CODE ###

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

ans_count =0

for i in range(10):
    for j in range(10):
        for k in range(10):
            i_pos = s.find(str(i))

            if i_pos < 0:
                continue

            j_pos = s.find(str(j),i_pos+1)

            if j_pos < 0:
                continue

            k_pos = s.find(str(k), j_pos +1)

            if k_pos < 0:
                continue

            ans_count += 1

print(ans_count)
### BUGGY CODE ###

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

h = int(m/n)+1
x = 0
for a in range(h, 0, -1):
    if a*n <= m:
        if m%a == 0:
            print(a)
            break
    else:
        continue

### FIXED CODE ###

import sys

def make_divisors(num):
    divisors = []
    for i in range(1, int(num**0.5)+1):
        if num%i == 0:
            divisors.append(i)
            if num//i != i:
                divisors.append(num//i)
    divisors.sort()
    return divisors

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

divisors = make_divisors(m)

for i in range(1, len(divisors)+1):
    if divisors[i*-1] * n <= m:
        print(divisors[i*-1])
        sys.exit()
### BUGGY CODE ###

n,m=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]

for i in range(m):
    a.sort()
    b=a.pop()
    b=b/2
    a.append(b)
c=[int(i) for i in a]

ans=0
for i in c:
    ans+=i
print(ans)

### FIXED CODE ###

import heapq
n,m=[int(i) for i in input().split()]
a=[-1*int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    b=heapq.heappop(a)
    b=b/2
    heapq.heappush(a,b)
ans=0
for i in a:
    ans-=int(i)
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
S = [int(input()) for _ in range(W)]
    
floor = list(range(0,H+1))

if S.count(1) >0:
	floor[1]=0
	floor[2]=1
if S.count(2) >0:
    floor[2]=0

for i in range (3, H+1):
		floor[i]=floor[i-2]*(1-S.count(i-2))+floor[i-1]*(1-S.count(i-1))
print(floor[H]%(10**9+7))

### FIXED CODE ###

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

A = []

for i in range (0, M):
	A.append(int(input()))


if N == 1:
	print(1)
	exit()
elif N ==2:
	if len(A) ==1:
		print(1)
	else:
		print(2)
	exit()

DP = [0]*N

if A.count(1)==0:
	DP[0] = 1

if A.count(2)==0:
	if A.count(1)==0:
		DP[1] = 2
	else:
		DP[1] = 1

for i in range (0, M):
	DP[A[i]-1] = -1

for i in range (0, 2):
	if DP[i] == -1:
		DP[i] = 0

for i in range (2, N):
	if DP[i] ==-1:
		DP[i] = 0
	else:
		DP[i] = DP[i-1] + DP[i-2]

print(DP[-1]%(1000000007))
### BUGGY CODE ###

from collections import Counter
n = int(input())
s = input()
ans = float('inf')

for i in range(n):
    a = Counter(s[:i])
    b = Counter(s[i+1:])

    ans = min(ans, a['W'] + b['E'])

print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = input()
e = int(s.count('E'))
ans = e

a = 0
for i in range(n):
    if s[i] == 'W':
        a += 1
    b = e - ((i+1)-a)
    ans = min(ans, a+b)


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

K = int(input())
i = 0
Num = 7

if K%2 == 0:
    print (-1)
else:
    while True:
        i += 1
        if Num % K == 0:
            print(i)
            break
        Num = Num*10 + 7
        


### FIXED CODE ###

K = int(input())
i = 1
Num = 7


if K%2 == 0 or K%5 == 0:
    print (-1)
else:
    while True:
        
        Num = Num % K
        if Num == 0:
            print(i)
            break
    
        while Num < K:
            Num = Num*10 + 7
            i += 1
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
# from numba import njit,i8


# @njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,l,r):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(i - A[i],0)
            r = min(i + A[i],N-1)
            B[l] += 1
            if r + 1 < N:
                B[r+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    return A


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

    if K >= 43:
        M = 43
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,l,r):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(i - A[i],0)
            r = min(i + A[i],N-1)
            B[l] += 1
            if r + 1 < N:
                B[r+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    return A


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

    if K >= 43:
        M = 43
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
b = []
for i in range(n):
    y = a.count(i + 1)
    if y != 0:
        b.append(y)
    else:
        b.append(0)
    x += y * (y - 1) / 2

for j in range(n):
    print(int(x - b[a[j] - 1] + 1))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
b = [0] * n
for i in range(n):
    b[a[i] - 1] += 1

x = 0
for j in range(n):
    x += ((b[j] - 1) * b[j] / 2)

for k in range(n):
    print(int(x - b[a[k] - 1] + 1))
### BUGGY CODE ###

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

ans = 0
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(N+1):
    for j in range(M+1):
        # if dp[i][j] + A[i] <= K:
        if i+1 < N+1:
            dp[i+1][j] = dp[i][j] + A[i]
            if dp[i+1][j] <= K:
                ans = max(ans, i+1+j)
        # if dp[i][j] + B[j] <= K:
        if j+1 < M+1:
            dp[i][j+1] = dp[i][j] + B[j]
            if dp[i][j+1] <= K:
                ans = max(ans, i+1+j)
        # if dp[i][j] + A[i] > K and dp[i][j] + B[j] > K:
        #     break
# print(dp)
print(ans)

### FIXED CODE ###

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

a = [0]
b = [0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i] +B[i])
ans = 0
j = M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K -a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

# 入力の取得(1行目。数値)
i = list(map(int, input().split()))

# 変数セット
# 1.配列[添字=人数、値=初期の点数]
points = [i[1]] * i[0]
# 2.正解数(引数の数)
correntCount = i[2]

# 正解数ループ
for i in range(correntCount):
    correcter = int(input()) - 1    
    #全てを1減算
    points = [ n - 1 for n in points]
    #正解者に1加算(正解者以外を減算するため)
    points[correcter] += 1

# 値が0以下の参加者は敗退(No)、1以上なら勝ち抜け(Yes)
for point in points:
    if point <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

# 入力の取得(1行目。数値)
i = list(map(int, input().split()))

# 変数セット
# 1.配列[値=初期の点数-★正解数(解説より)★、個数=人数]
points = [i[1]- i[2]] * (i[0] )
# 2.正解数(引数の数)
correntCount = i[2]

# 正解数ループ
for i in range(correntCount):
    correcter = int(input()) - 1    
    #正解者に1加算
    points[correcter] += 1

# 値が0以下の参加者は敗退(No)、1以上なら勝ち抜け(Yes)
for point in points:
    if point <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

#coding:utf-8

S = input()


def irekae(str):
    return str.replace('BW', 'WB', 1)


count = 0
while 'BW' in S:
    S = irekae(S)
    count += 1

print(count)


### FIXED CODE ###

#coding:utf-8

S = input()

margin = 0
for i, moji in enumerate(S):
    if moji == 'B':
        margin = i
        break

idx_list = []
for i, moji in enumerate(S[margin:]):
    if moji == 'W':
        idx_list.append(i)

q = len(idx_list) - 1
print(sum(idx_list) - int(0.5 * q * (q + 1)))
### BUGGY CODE ###

def modpow(a: int, p: int, mod: int) -> int:
    # return a**p (mod MOD) O(log p)
    if p == 0:
        return 1
    if p % 2 == 0:
        half = modpow(a, p//2, mod)
        return half*half % mod
    else:
        return a * modpow(a, p-1, mod) % mod


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

ret = 0
cnt_1 = [0] * 60

for item in a_ls:
    for i in range(60):
        if len(bin(item)) <= i:
            continue
        elif bin(item)[-1-i] == '1':
            cnt_1[i] += 1

for i in range(60):
    tmp = ((n - cnt_1[i]) * cnt_1[i])
    tmp %= 10 ** 9 + 7
    tmp *= modpow(2, i, 10 ** 9 + 7)
    ret += tmp
    ret %= 10 ** 9 + 7

print(ret)


### FIXED CODE ###

def str2bitstr(chs):
    val = int(chs)
    tmp = bin(val)[2:]
    tmp2 = '0' * (60 - len(tmp))
    return tmp2 + tmp


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

cnts = [0] * 60

for item in a:
    for i, ch in enumerate(item):
        if ch == '1':
            cnts[i] += 1

ret = 0
now = 1

for i in range(1, 61):
    kumi = cnts[-i] * (n - cnts[-i]) % (10 ** 9 + 7)
    ret += kumi * now % (10 ** 9 + 7)
    now *= 2 % (10 ** 9 + 7)
    ret = ret % (10 ** 9 + 7)

print(ret % (10 ** 9 + 7))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
i = 0
ans = 0
if 0 in a:
    print(0)
else:
    while ans<10**10 and i<len(a):
        ans*=a[i]
    if (ans<=10**18):
        print(ans)
    else:
        print(-1)


### FIXED CODE ###

i = 0
ans = 1
n = int(input())
a = list(map(int, input().split()))
if 0 in a:
    print(0)
else:
    while ans<10**18 and i<len(a):
        ans*=a[i]
        i+=1
    if (ans<=10**18):
        print(ans)
    else:
        print(-1)
### BUGGY CODE ###

X = input()
X_length = len(X)
change = True
while change:
    X = X.replace("ST", "", 1)
    change = len(X) != X_length
    X_length = len(X)
print(X_length)


### FIXED CODE ###

X = input()
stack = []
for s in X:
    if s == "S":
        stack.append(s)
    elif s == "T":
        if len(stack) == 0 or stack[-1] == "T":
            stack.append(s)
        else:
            stack.pop(-1)
print(len(stack))
### BUGGY CODE ###

import heapq
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    N,M=map(int,input().split())
    A=sorted(list(map(int,input().split())))
    B, C = [0] * M, [0] * M
    for i in range(M):
        B[i], C[i] = map(int, input().split())



    L=[]
    for i in range(M):
        for _ in range(B[i]):
            L.append(C[i])
    L.sort()
    ans=list(heapq.merge(A,L))
    print(sum(ans[len(ans)-N:]))




resolve()

### FIXED CODE ###

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

for _ in range(M):
  B, C = map(int, input().split())
  A[C] += B

A = sorted(A.items(), key=lambda x:x[0], reverse=True)

ans = 0
for key, count in A:
  if N > count:
    ans += key * count
    N -= count
  else:
    ans += key * N
    break

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

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

  if N == 2:
    print(abs(h[1] - h[0]))
    exit()

  DP = [0 for i in range(N)]

  mi = min(N, K + 1)
  for i in range(1, mi):
    DP[i] = abs(h[i] - h[0])
  for i in range(1, N - 1):
    mi = min(N, i + K)
    for j in range(i, mi):
      t = DP[i] + abs(h[j] - h[i])
      if DP[j] > t:
        DP[j] = t
    if i + K <= N - 1:
      DP[i+K] = DP[i] + abs(h[i+K] - h[i])
  print(DP[N-1])
  
main()

### FIXED CODE ###

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

  if N == 2:
    print(abs(h[1] - h[0]))
    exit()

  DP = [0 for i in range(N)]

  mi = min(N, K + 1)
  for i in range(1, mi):
    DP[i] = abs(h[i] - h[0])
  for i in range(1, N - 1):
    mi = min(N, i + K)
    for j in range(i, mi):
      t = DP[i] + abs(h[j] - h[i])
      if DP[j] > t:
        DP[j] = t
    if i + K <= N - 1:
      DP[i+K] = DP[i] + abs(h[i+K] - h[i])
  print(DP[N-1])
  
main()
### BUGGY CODE ###

N, K, Q = map(int, input().split(" "))
persons = list()

for i in range(N):
    persons.append(K)

for i in range(Q):
    a = int(input())
    for j in range(N):
        if a != j:
            persons[j-1] -= 1

for person in persons:
    if person <= 0:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

N, K, Q = map(int, input().split(" "))
persons = [K-Q] * N

for i in range(Q):
    a = int(input())
    persons[a-1] += 1

for person in persons:
    if person <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
S=[]
d=sum(A)//len(A)+1
for b in range(-d,d):
    s=0
    for i in range(N):
        s+=abs(A[i]-b-i)
    S.append(s)
print(min(S))

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
u=[]
for i in range(N):
    u.append(A[i]-i)
a=sorted(u)
if len(a)%2==0:
    p=a[len(a)//2]
else:
    p=a[len(a)//2]
ans=0
for j in range(N):
    ans+=abs(a[j]-p)
print(ans)
### BUGGY CODE ###

import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import collections


class BellmanFord():
    def __init__(self):
        self.edges = []

    def add(self, u, v, d, directed=False):
        """
        u = from, v = to, d = cost
        directed = Trueのとき、有向グラフである。
        """
        if directed is False:
            self.edges.append([u, v, d])
            self.edges.append([v, u, d])
        else:
            self.edges.append([u, v, d])

    def BellmanFord_search(self, s):
        """
        次のBellmanFord_negative_boolまで考慮した時には、0-indexedであることに注意
        s =  始点
        return: d[i] 始点sから各点iまでの最短経路
        """
        d = collections.defaultdict(lambda: float('inf'))
        d[s] = 0
        numEdges = len(self.edges)
        while True:
            update = False
            for i in range(numEdges):
                e = self.edges[i]
                # e: 辺iについて [from,to,cost]
                if d[e[0]] != float("inf") and d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    update = True
            if not update:
                break
        return d

    def BellmanFord_negative_bool(self, numNodes, zero_indexed=False):
        # 負の閉路の検出, Trueなら負の閉路が存在する
        d = collections.defaultdict(lambda: float('inf'))
        d[0] = 0
        numEdges = len(self.edges)
        for i in range(numNodes):
            for j in range(numEdges):
                e = self.edges[j]
                if d[e[1]] > d[e[0]] + e[2]:
                    d[e[1]] = d[e[0]] + e[2]
                    if i == numNodes-1:
                        return True
        return False

g = BellmanFord()
n = ni()

for i in range(n-1):
    u,v,w = na()
    g.add(u,v,w)

d = g.BellmanFord_search(1)

for i in range(1,n+1):
    if d[i] % 2 ==0:
        print(0)
    else:
        print(1)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
g = [[] for i in range(n)]

for i in range(n-1):
    u,v,w = na()
    g[u-1].append((v-1,w))
    g[v-1].append((u-1,w))

dp = [0]*n

def f(a,b,c):
    dp[b] = c
    for i,j in g[b]:
        if i != a:
            f(b,i,c+j)

f(0,0,0)

for k in dp:
    print(k%2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
ans=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        ans[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
for i in range(q):
    s=0
    for j in range(l[i]+d-1,r[i],d):
        s+=abs(ans[j][0]-ans[j-d][0])+abs(ans[j][1]-ans[j-d][1])
    print(s)

### FIXED CODE ###

import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
ans=[0]*(h*w)
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(A[i][0]-A[i-d][0])+abs(A[i][1]-A[i-d][1])
for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])