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

import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])
            
def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    for i in range(len(edge)):
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
            if n < 1: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n
dist = [[0] * n for _ in range(n)]
 
for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)
    
x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])
 
edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))
    
del x, y
print(kruskal(n, edge))

### FIXED CODE ###

import heapq
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            self.rank[x] += (self.rank[x] == self.rank[y])

def kruskal(n, edge):
    ans = 0
    uf = UnionFind(n)
    while True:
        d, v, u = heapq.heappop(edge)
        
        if uf.find(v) != uf.find(u):
            uf.union(v, u)
            n -= 1
            ans += d
        if n < 2: return ans
    return ans

n = int(input())
x, y = [None]*n, [None]*n

for i in range(n):
    a, b = map(int, input().split())
    x[i] = (a, i)
    y[i] = (b, i)

x.sort(key=lambda x:x[0])
y.sort(key=lambda y:y[0])

edge = []
for i in range(n-1):
    heapq.heappush(edge, (x[i+1][0]-x[i][0], x[i][1], x[i+1][1]))
    heapq.heappush(edge, (y[i+1][0]-y[i][0], y[i][1], y[i+1][1]))

del x, y
print(kruskal(n, edge))
### BUGGY CODE ###

N=int(input())
A=[]
for _ in range(N):
    a=int(input())
    if a not in A:
        A.append(a)
    else:
        A.remove(a)
print(len(A))

### FIXED CODE ###

N=int(input())
A=set()
for _ in range(N):
    a=int(input())
    if a not in A:
        A.add(a)
    else:
        A.remove(a)
print(len(A))
### BUGGY CODE ###

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

A_list = []

for _ in range(Q):
    A_list.append(int(input()))

for n in range(1, N + 1):
    n_lost_point = Q - A_list.count(n)
    if n_lost_point < K:
        ans = 'Yes'
    else:
        ans = 'No'
    print(ans)

### FIXED CODE ###

import collections

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

A_list = []

for _ in range(Q):
    A_list.append(int(input()))

A_list_collections = collections.Counter(A_list)
    
for n in range(1, N + 1):
    n_lost_point = Q - A_list_collections[n]
    if n_lost_point < K:
        ans = 'Yes'
    else:
        ans = 'No'
    print(ans)
### BUGGY CODE ###

from statistics import median
N = int(input())
A = list(map(int, input().split()))
B = list()
sad = 0

for i in range(N):
  B.append(A[i]-i)

  b = median(B)

for i in range(N):
  sad = sad + abs(A[i] - (b+i))

print(int(sad))

### FIXED CODE ###

from statistics import median
N = int(input())
A = list(map(int, input().split()))
B = list()
sad = 0

for i in range(N):
  B.append(A[i]-i)

b = median(B)

for i in range(N):
  sad = sad + abs(A[i] - (b+i))

print(int(sad))
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(a,b+1):
    if i-a<k or b-i<k:print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
if b-a+1<=2*k:
    for i in range(a,b+1):print(i)
else:
    for i in range(a,a+k):print(i)
    for i in range(b-k+1,b+1):print(i)
### BUGGY CODE ###

N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
dp=[1]*(N+1)
if 1 in a:
  dp[1]=0
else:
  dp[1]=1
for i in range(2,N+1):
  if i in a:
    dp[i]=0
  else:
    dp[i]=dp[i-1]+dp[i-2]
  dp[i]%=1000000007
print(dp[N])




### FIXED CODE ###

N,M=map(int,input().split())
dp=[1]*(N+1)
for _ in range(M):
  i=int(input())
  dp[i]=0
for i in range(2,N+1):
  if dp[i]!=0:
      dp[i]=dp[i-1]+dp[i-2]
  dp[i]%=1000000007
print(dp[N])
### BUGGY CODE ###

n = int(input())

l = list(map(int,input().split()))
l.sort()
ans = [1 for a in range(n-2) for b in range(a+1,n-1) for c in range(b+1,n) if l[a]+l[b]>l[c] and l[b]+l[c]>l[a] and l[c]+l[b]>l[a]]
print(sum(ans))


### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
count = 0
l.sort()

def binary_search(key,l,n):
    key_number = int((n-1)//2)
    L = 0
    R = n-1
    while True:
        if l[key_number] < key:
            L = key_number
            key_number = (L+R)//2
        else:
            R = key_number
            key_number = (L+R)//2

        if key == l[key_number]:
            return key_number
        if (R-L) == 1:
            return L+1

def binary_search(key,l,n):
    L = 0
    R = n-1
    while L < R:
        key_number = int((n-1)//2)
        if l[key_number] < key:
            L = key_number + 1
        else:
            R = key_number
    return key_number

ans = 0
#print(binary_search(7+8,l,n))

for i in range(n-2):
    for j in range(i+1,n-1):
        a = l[i]
        b = l[j]

        ans += bisect.bisect_left(l,a+b)- j -1

        #print("{} <c< {} b-a = {} a+b = {}".format(key_numberL,key_numberR,b-a,a+b))

        #print('i={} j={} key_numberL={} key_numberR={} count={}'.format(i,j,key_numberL,key_numberR,-key_numberL-double_count))
        #count += key_numberR-key_numberL-double_count
print(ans)
### BUGGY CODE ###

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

dp = [10 ** 10] * n
dp[0] = 0

for i in range(1, n):
    for j in range(1, min(k + 1, n)):
        cost = abs(h[i] - h[i - j])
        dp[i] = min(dp[i], dp[i - j] + cost)

print(dp[n - 1])


### FIXED CODE ###

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

dp = [10 ** 10] * (n + k)
h += [10 ** 10] * k
dp[0] = 0

for i in range(n):
    for j in range(1, k + 1):
        cost = abs(h[i] - h[i + j])
        dp[i + j] = min(dp[i + j], dp[i] + cost)

print(dp[n - 1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
count = []
for x in a:
  tmp = 0
  for i in a:
    if x == i:
      tmp += 1
    elif abs(x - i) == 1:
      tmp += 1
    else:
      continue
  count.append(tmp)
print(max(count))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
count = {}
for i in a:
  for j in [-1, 0, 1]:
    count.setdefault(i+j, 0)
    count[i+j] += 1
  
print(max(count.values()))
### BUGGY CODE ###

import itertools

N, M, R = map(int, input().split())
r = [int(s) - 1 for s in input().split()]
a, b, c = [0] * M, [0] * M, [0] * M
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

wf = [[float('inf')] * N for _ in range(N)]
for i in range(M):
    wf[a[i]][b[i]] = c[i]
    wf[b[i]][a[i]] = c[i]

for k, i, j in itertools.product(range(N), repeat=3):
    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

x = float('inf')
for route in itertools.permutations(r):
    y = sum(wf[route[i]][route[i + 1]] for i in range(R - 1))
    x = min(x, y)

print(x)

### FIXED CODE ###

import itertools

N, M, R = map(int, input().split())
r = [int(s) - 1 for s in input().split()]
a, b, c = [0] * M, [0] * M, [0] * M
for i in range(M):
    a[i], b[i], c[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

wf = [[float('inf')] * N for _ in range(N)]
for i in range(M):
    wf[a[i]][b[i]] = c[i]
    wf[b[i]][a[i]] = c[i]

for k, i, j in itertools.product(range(N), repeat=3):
    wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

x = float('inf')
for route in itertools.permutations(r):
    y = sum(wf[route[i]][route[i + 1]] for i in range(R - 1))
    x = min(x, y)

print(x)
### BUGGY CODE ###

n,k = [int(x) for x in input().split()]
s = {}

for i in input().split():
    if(i in s):
        s[i] += 1
    else:
        s[i] = 1


t = list(s.values())
t.sort()
a = 0

while len(t) > k:
    a += t.pop(0)

print(a)


### FIXED CODE ###

n,k = [int(x) for x in input().split()]
s = {}

for i in input().split():
    if(i in s):
        s[i] += 1
    else:
        s[i] = 1


t = list(s.values())
t.sort()
a = sum(t[0:-k])

print(a)
### BUGGY CODE ###

S = input()
S = S[::-1]
#簡単にするためにひっくり返す
N = len(S)

A=[0]*2019
number=0
A[0]=1
#０を２０１９で割った余りは０
d=1

ans=0

for i in S:
  number+=int(i)*d
  A[number%2019]+=1
  d=10*d

for i in A:
  ans+=i*(i-1)//2

print(ans)



### FIXED CODE ###

S = input()
S = S[::-1]
#簡単にするためにひっくり返す
N = len(S)

A=[0]*2019
number=0
A[0]=1
#０を２０１９で割った余りは０
d=1

ans=0

for i in S:
  number+=int(i)*d
  A[number%2019]+=1
  d=10*d
  d=d%2019

for i in A:
  ans+=i*(i-1)//2

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

import re

NQ = [int(i) for i in input().split()]
N = NQ[0]
Q = NQ[1]
S = input()
LR = [[int(i) for i in input().split()] for j in range(Q)]
check = [0] * (N - 1)
for i in range(N - 1):
    check[i] = 1 if S[i:i + 2] == "AC" else 0

for j in range(Q):
    print(sum(check[LR[j][0] - 1:LR[j][1] - 1]))


### FIXED CODE ###

import re

NQ = [int(i) for i in input().split()]
N = NQ[0]
Q = NQ[1]
S = input()
LR = [[int(i) for i in input().split()] for j in range(Q)]
check = [0] * N
for i in range(N - 1):
    check[i + 1] = check[i] + (1 if S[i:i + 2] == "AC" else 0)


for j in range(Q):
    print((check[LR[j][1] - 1]) - (check[LR[j][0] - 1]))
### BUGGY CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
x = A[:]
k = -1
for _ in range(N):
    x = x[1:] + x[:1]
    diff = sum([min(K - abs(x[i] - x[i+1]), abs(x[i] - x[i+1])) for i in range(N - 1)])
    if k == -1 or k > diff:
        k = diff
print(k)

### FIXED CODE ###

K, N = map(int, input().split())
A = list(map(int, input().split()))
diff = [min(K - abs(A[i] - A[i+1]), abs(A[i] - A[i+1])) for i in range(-1, N - 1)]
diff.sort()
print(sum(diff) - diff[-1])
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
bigp = 10**9+7
L1 = []
L2 = []
p = 2
max = M
K = M
while p <= max:
    if K%p == 0:
        L1.append(p)
        K = K//p
        if p not in L2:
            L2.append(p)
    else:
        p = p+1

ans = 1
def ModComb(n, r, p):
    N = n%p
    R = r%p
    if N<R:
        return 0
    if N < 2*R:
        R = N-R
    if R == 0:
        return 1
    else:
        return (n*pow(r, p-2, p))%p*ModComb(n-1, r-1, p)


for x in L2:
    primepower = L1.count(x)
    ans *= ModComb(N+primepower-1, primepower, bigp)%bigp

print(ans%bigp)

### FIXED CODE ###

N, M = map(int, input().split())
bigp = 10**9+7
L = []
p, power = 2, 0
K = M
while p*p <= K:
    while K%p == 0:
        K = K//p
        power += 1
    if power > 0:
        L.append([p, power])
    if p == 2:
        p += 1
    else:
        p += 2
    power = 0
if K > 1:
    L.append([K, 1])


ans = 1
def ModComb(n, r, p):
    N = n%p
    R = r%p
    if N<R:
        return 0
    if N < 2*R:
        R = N-R
    if R == 0:
        return 1
    else:
        return (n*pow(r, p-2, p))%p*ModComb(n-1, r-1, p)


for i in range(len(L)):
    power = L[i][1]
    ans *= ModComb(N+power-1, power, bigp)
    ans %= bigp

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

from collections import defaultdict
from fractions import Fraction

N = int(input())

MOD = 1000000007
d_plus = defaultdict(int)  # + or ∞
d_minus = defaultdict(int)  # - or 0
ans = 1
ans_00 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        ans_00 += 1
    elif a == 0:
        d_minus[0] += 1
    elif b == 0:
        d_plus[float('inf')] += 1
    elif a * b > 0:
        d_plus[Fraction(a, b)] += 1
    else:
        d_minus[Fraction(a, b)] += 1


def pair(p):
    if p == 0:
        return float('inf')
    elif p == float('inf'):
        return 0
    else:
        return -1 / p


for m in d_minus:
    d_plus[pair(m)] += 0
for p in d_plus:
    ans *= (pow(2, d_plus[p], MOD) + pow(2, d_minus[pair(p)], MOD) - 1)
    ans %= MOD
print((ans - 1 + ans_00) % MOD)


### FIXED CODE ###

from collections import defaultdict
from math import gcd

N = int(input())

MOD = 1000000007
d_plus = defaultdict(int)  # + or ∞
d_minus = defaultdict(int)  # - or 0
ans = 1
ans_00 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        ans_00 += 1
    elif a == 0:
        d_minus[0] += 1
    elif b == 0:
        d_plus[float('inf')] += 1
    else:
        g = gcd(a, b)
        if (a > 0) ^ (b > 0):
            d_plus[(abs(a // g), abs(b // g))] += 1
        else:
            d_minus[(abs(a // g), -abs(b // g))] += 1


def pair(p):
    if p == 0:
        return float('inf')
    elif p == float('inf'):
        return 0
    else:
        a, b = -p[1], p[0]
        if a < 0:
            a, b = -a, -b
        return a, b


for m in d_minus:
    d_plus[pair(m)]
for p in d_plus:
    ans *= (pow(2, d_plus[p], MOD) + pow(2, d_minus[pair(p)], MOD) - 1)
    ans %= MOD
print((ans - 1 + ans_00) % MOD)
### BUGGY CODE ###

from operator import mul
from functools import reduce
import math

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

so=10**9+7

large=(pow(2,n,so)-1) % so 

def kumiawase(n,r):
    return int(math.factorial(n) / (math.factorial(n-r) * math.factorial(r)))

ajogai = kumiawase(n,a) % so
bjogai = kumiawase(n,b) % so
print((large  - ajogai - bjogai + 2*so) % so)

### FIXED CODE ###

from operator import mul
from functools import reduce
import math

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

so=10**9+7

large=(pow(2,n,so)-1)

def kumiawase(n,r):
    over=1
    for i in range(r):
        over *= n-i
        over %= so
    under = math.factorial(r)
    return over * pow(under,so-2,so)

ajogai = kumiawase(n,a) % so
bjogai = kumiawase(n,b) % so
print((large - ajogai - bjogai + 2*so) % so)
### BUGGY CODE ###

from sys import stdin
#for _ in range(n):
#  x, y, z = map(int, stdin.readline().split())

n,m=map(int,stdin.readline().split())

uf=[i for i in range(n+1)]

def uff(x):
    while x!=uf[x]:
        x=uf[x]
    return x

for i in range(m):
    a,b= map(int, stdin.readline().split())
    ua=uff(a)
    ub=uff(b)
    if ua<ub:
        uf[ub]=ua
    else:
        uf[ua]=ub

cnt=[0 for i in range(n+1)]
for i in range(1,n+1):
    cnt[uff(i)]+=1
print(max(cnt))

### FIXED CODE ###

import sys
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
 
 
if __name__ == '__main__':
    sys.setrecursionlimit(1000000)
    n,m=map(int,sys.stdin.readline().split())
    ins = UnionFind(n+1)
    for i in range(m):
        a,b= map(int, sys.stdin.readline().split())
        ins.union(a,b)
    """
    ins.union(0, 1)
    ins.union(2, 3)
    print(ins.find(0, 3))  # False
    ins.union(1, 2)
    print(ins.find(0, 3))  # True
    """
    cnt=[0 for i in range(n+1)]
    for i in range(1,n+1):
        cnt[ins._root(i)]+=1
    print(max(cnt))
### BUGGY CODE ###

#!/usr/bin/env python3

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

num_list = []
r, g, b = 0, 0, 0
for i in range(n-1, -1, -1):
    if s[i] == "R":
        r += 1
    elif s[i] == "G":
        g += 1
    elif s[i] == "B":
        b += 1
    num_list.append([r, g, b])

num_list.reverse()

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] == s[j]:
            continue
        rest_str = "B"
        dev = [s[i], s[j]]
        dev.sort()
        if ["B", "G"] == dev:
            rest_num = 0
            rest_str = "R"
        elif ["B", "R"] == dev:
            rest_num = 1
            rest_str = "G"
        elif ["G", "R"] == dev:
            rest_num = 2
            rest_str = "B"

        ans += num_list[j+1][rest_num]
        if j+j-i < n:
            if s[j+j-i] == rest_str:
                ans -= 1

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

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

num_list = []
r, g, b = 0, 0, 0
for i in range(n-1, -1, -1):
    if s[i] == "R":
        r += 1
    elif s[i] == "G":
        g += 1
    elif s[i] == "B":
        b += 1
    num_list.append([r, g, b])

num_list.reverse()

ans = 0
for i in range(n-2):
    if s[i] == "R":
        ans += num_list[i+1][1] * num_list[i+1][2]  # G , B
        for j in range(0, (n-i-1)//2):
            a, b, c = i, j+i+1, j+j+i+2
            # print(a, b, c)
            if {s[b], s[c]} == {"G", "B"}:
                ans -= 1
    if s[i] == "G":
        ans += num_list[i+1][0] * num_list[i+1][2]  # R, B
        for j in range(0, (n-i-1)//2):
            a, b, c = i, j+i+1, j+j+i+2
            # print(a, b, c)
            if {s[b], s[c]} == {"R", "B"}:
                ans -= 1
    if s[i] == "B":
        ans += num_list[i+1][0] * num_list[i+1][1]  # R, G
        for j in range(0, (n-i-1)//2):
            a, b, c = i, j+i+1, j+j+i+2
            # print(a, b, c)
            if {s[b], s[c]} == {"R", "G"}:
                ans -= 1
# print(num_list)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = {}
for i in range(n):
    x = int(input())
    if x in h.keys():
        h[x] += 1
    else:
        h[x] = 1

res = max(h.keys()) - min(h.keys())
ih = sorted(h.keys())

for i in range(len(h)):
    hi = ih[i]
    cnum = h[hi]
    ip = i+1
    if cnum >= k:
        d = 0
        res = 0
        break
    else:
        d = max(h.keys()) - min(h.keys())
    while cnum < k and ip < len(h):
        hi2 = ih[ip]
        cnum += h[hi]
        ip += 1
        if cnum >= k:
            d = abs(hi - hi2)
    res = min(res, d)

print(res)

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()
res = [h[i+k-1]-h[i] for i in range(n-k+1) ]
print(min(res))
### BUGGY CODE ###

import numpy as np

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

B = A.copy()
discount_cnt = np.zeros(N)

for i in range(M):
    tmp = B / 2
    tmp_idx = np.argmax(tmp)
    discount_cnt[tmp_idx] += 1
    B[tmp_idx] = tmp[tmp_idx]

tmp_arr = np.array([2 ** i for i in discount_cnt])
print(int(np.sum(np.floor(A / tmp_arr))))


### FIXED CODE ###

import heapq


N, M = map(int, input().split())
A = list(map(int, input().split()))
A_inv = [-a for a in A]
heapq.heapify(A_inv)
for _ in range(M):
    max_inv = heapq.heappop(A_inv)
    heapq.heappush(A_inv, -(-max_inv//2))

print(sum([-a for a in A_inv]))
### BUGGY CODE ###

N=int(input())
S=input()

ans = S.count("R")*S.count("G")*S.count("B")

tmp=0

for i in range(N):
  for j in range(i,N):
    if j-i+j < N:
      if len(set([S[i],S[j],S[j-i+j]]))==3:
        tmp += 1

ans = ans - tmp
print(ans)

### FIXED CODE ###

N=int(input())
S=input()

ans = S.count("R")*S.count("G")*S.count("B")

tmp=0

for i in range(N):
  for j in range(i,N):
    if j-i+j < N:
      if S[i]!=S[j] and S[j]!=S[j-i+j] and S[i]!=S[j-i+j]:
        tmp += 1

ans = ans - tmp
print(ans)
### BUGGY CODE ###

L,R=map(int,input().split())
R=min(R,L+4038)
ans=2020
for i in range(L,R+1):
    for j in range(L,R+1):
        if i!=j: ans=min(ans,(i*j)%2019)
print(ans)

### FIXED CODE ###

L,R=map(int,input().split())
R=min(R,L+4038)
ans=2020
for i in range(L,R+1):
    for j in range(L,R+1):
        if i!=j: ans=min(ans,(i*j)%2019)
print(ans)
### BUGGY CODE ###

N=int(input())
line=input()
line=line.rstrip().split(" ")
list1=[]
for i in range(N):
    list1.append(int(line[i])-i-1)
#print(list1)

list2=[]
list3=[]
for j in range(2):
    for k in range(N):
        list2.append(abs(list1[k]-1-j))
        
    list3.append(sum(list2))
    list2=[]
#print(list3)

if list3[0]==list3[1]:
    print(list3[0])
elif list3[0]<list3[1]:
    list2=[]
    list3=[]
    count=100000000000000000
    for l in range(1000000000):
        for m in range(N):
            list2.append(abs(list1[m]-1+l))
        if count>=sum(list2):
            count=sum(list2)
            #print(list2)
            list2=[]
            l=l+10
        else:
            count=100000000000000000
            for n in range(l,l+11):
                for o in range(N):
                    list2.append(abs(list1[o]-1+(n-10)))
                if count>=sum(list2):
                    count=sum(list2)
                    list2=[]
                else:
                    print(count)
                    break
            break        
            
        
else: 
    list2=[]
    list3=[]
    count=100000000000000000
    for l in range(1000000000):
        for m in range(N):
            list2.append(abs(list1[m]-1-l))
        if count>=sum(list2):
            count=sum(list2)
            list2=[]
            l=l+10
        else:
            count=100000000000000000
            for n in range(l,l+11):
                for o in range(N):
                    list2.append(abs(list1[o]-1+(n-10)))
                if count>=sum(list2):
                    count=sum(list2)
                    list2=[]
                else:
                    print(count)
                    break
            break             
        

### FIXED CODE ###

N=int(input())

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

if N==1:
    print(0)
    exit()
elif N==2:
    B=[A[0]-1,A[1]-2]
    b=sum(B)//2
else:
    B=[]
    for i in range(N):
        B.append(A[i]-(1+i))
    #print(B)
    B.sort()
    #print(B)
    b=B[N//2]

ans=0
for i in range(N):
    ans+=abs(A[i]-(b+1+i))
print(ans)
### BUGGY CODE ###

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


nums=[]
for i in range(a,b+1):
    nums.append(i)
#print(nums)
nums2=sorted(nums,reverse=True)
#print(nums2)

if k>=b-a+1:
    for x in nums:
        print(x)
else:
    ans=[]
    for j in range(k):
        ans.append(nums[j])
        ans.append(nums2[j])

    ans=sorted(set(ans))

    #print(ans)

    for l in ans:
        print(l)


### FIXED CODE ###

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

if b-a+1>=2*k:
    aa=[a+i for i in range(k)]
    bb=[b-i for i in range(k)]
    cc=sorted(aa+bb)
    for s in cc:
        print(s)
else:
    for n in range(a,b+1):
        print(n)
### BUGGY CODE ###

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

flag = False
a_total = 0
for i in range(N):
    a_total += A[i]
    if a_total > K:
        flag = True
        break

if flag:
    a_max = i
    ans = a_max
else:
    a_max = N
    ans = N

for i in range(a_max+1)[::-1]:
    total = sum(A[:i])
    #print('b total: ', total)
    flag = False
    for j in range(M):
        total += B[j]
        #print('a total: ', total)
        if total > K:
            flag = True
            break
    if flag:
        ans = max(ans, i + j)
    else:
        ans = max(ans, i + j + 1)
    #print('ans: ', ans)
    #print()

print(ans)

### FIXED CODE ###

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

a, b = [0]*N, [0]*M

total = 0
for i in range(N):
    total += A[i]
    a[i] = total

a = [0] + a

total = 0
for i in range(M):
    total += B[i]
    b[i] = total

b = [0] + b

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

print(ans)