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

n = int(input())
hlist = list(map(int, input().split()))
alist = list(range(1, n+1))

ans = 0
# The absolute difference of their attendee numbers is equal to the sum of their heights.
for i, h1 in enumerate(hlist):
    for j, h2 in enumerate(hlist):
        if h2>n or h1>n or h1+h2>n:
            continue
        if abs(i-j) == h1+h2:
            ans += 1

print(ans//2)

        



### FIXED CODE ###

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

cnt_ind_minus_height = {}
cnt_height_plus_ind = {}
cnt_height_minus_ind = {}
cnt_minus_height_minus_ind = {}

for ind in range(n):
    height = hlist[ind]
    if ind - height not in cnt_ind_minus_height:
        cnt_ind_minus_height[ind - height] = 0
    cnt_ind_minus_height[ind - height] += 1

    if ind + height not in cnt_height_plus_ind:
        cnt_height_plus_ind[ind + height] = 0
    cnt_height_plus_ind[ind + height] += 1

    if height-ind not in cnt_height_minus_ind:
        cnt_height_minus_ind[height-ind] = 0
    cnt_height_minus_ind[height-ind] += 1

    if -ind - height not in cnt_minus_height_minus_ind:
        cnt_minus_height_minus_ind[-height-ind] = 0
    cnt_minus_height_minus_ind[-height-ind] += 1

ans = 0
# Hi - i = - (Hj + j)
for val in cnt_height_minus_ind:
    if val in cnt_minus_height_minus_ind:
        ans += cnt_height_minus_ind[val]*cnt_minus_height_minus_ind[val]

# Hi + i = j - Hj
for val in cnt_height_plus_ind:
    if val in cnt_ind_minus_height:
        ans += cnt_height_plus_ind[val]*cnt_ind_minus_height[val]

# as we double count the pair
print(ans//2)
### BUGGY CODE ###

n,q = (int(i) for i in input().split())
s = input()
query = [0]*n
point = [0]*(n+1)
for i in range(n-1):
  if s[i] == 'A' and s[i+1] =='C': 
    query[i] = 1
  if s[i] == 'C' and s[i+1] =='A':
    point[i+1] -= 1
#print(point)
    
for i in range(q):
  l,r = (int(i) for i in input().split())
  ans = sum(query[(l-1):r])
  ans += point[r-1]
  print(ans)
 

### FIXED CODE ###

n,q = (int(i) for i in input().split())
s = input()
query = [0]*(n+1)
point = [0]*(n+1)
ct = 0
for i in range(n-1):
  if s[i] == 'A' and s[i+1] =='C': 
    ct += 1
    point[i] = -1 
  query[i+1] = ct
query[i+2] = ct  
#print(point)
    
for i in range(q):
  l,r = (int(i) for i in input().split())
  ans = query[r]-query[l-1]
  ans += point[r-1]
  print(ans)
### BUGGY CODE ###

import collections

num = int(input())
s = sorted(list(map(int, input().split())))
if num == 1:
    print(1)
else:
    max_ans = 0
    for i in range(num):
        start = s[i]
        c = collections.Counter(s)
        current_ans = c[start]+c[start+1]+c[start+2]
        max_ans = max(current_ans,max_ans)
        i += c[start]
    print(max_ans) 

### FIXED CODE ###

import collections

num = int(input())
s = sorted(list(map(int, input().split())))
if num == 1:
    print(1)
else:
    c = collections.Counter(s)
    max_ans = 0
    for i in range(num):
        start = s[i]
        current_ans = c[start]+c[start+1]+c[start+2]
        max_ans = max(current_ans,max_ans)
        i += c[start]
    print(max_ans)
### BUGGY CODE ###

import math

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

max = -1
for x in range(n+1):
    value = math.floor(a * x / b) - a * math.floor(x / b)
    if value > max:
        max = value

print(max)


### FIXED CODE ###

import math

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

x = b - 1
if x > n:
    x = n

result = math.floor(a * x / b) - a * math.floor(x / b)
print(result)
### BUGGY CODE ###

"""C."""

import sys

input = sys.stdin.readline  # noqa: A001

n = int(input())
a = list(map(int, input()[:-1].split(' ')))

MOD_VALUE = pow(10, 9) + 7
result = 0

for i in range(n - 1):
    result += a[i] * sum(a[i + 1:])

if result < MOD_VALUE:
    print(result)
else:
    print(result % MOD_VALUE)


### FIXED CODE ###

"""C."""

import sys

input = sys.stdin.readline  # noqa: A001

n = int(input())
a = list(map(int, input()[:-1].split(' ')))

MOD_VALUE = 10**9 + 7
result = 0

a_sum = sum(a)

for i, v in enumerate(a):
    result += v * (a_sum - v)
    a_sum -= v

if result < MOD_VALUE:
    print(result)
else:
    print(result % MOD_VALUE)
### BUGGY CODE ###

s=input()
t=input()
ct=0
for i in range(0,len(s)):
    if(s[i]!=t[i]):
            s=s.replace("t[i]","i")
            ct=ct+1
print(ct)

### FIXED CODE ###

s=input()
t=input()
ct=0
for i in range(0,len(s)):
    if(s[i]!=t[i]):
            
            ct=ct+1
print(ct)
### BUGGY CODE ###

#https://atcoder.jp/contests/abc098/tasks/arc098_a

n = int(input())
def process(x):
    if x=='E':
        return 0
    else:
        return 1
data = list(map(process, list(input())))

cumul = [0 for _ in range(n)]
for i in range(n):
    cumul[i] = data[:i+1].count(0)
cumul.insert(0, 0)

costs = [0 for _ in range(n)]
for i in range(n):
    cost = 0
    cost += i-cumul[i]
    cost += cumul[n]-cumul[i+1]
    costs[i] = cost

print(min(costs))


### FIXED CODE ###

#https://atcoder.jp/contests/abc098/tasks/arc098_a

n = int(input())
d = input()

pre = d[1:].count('E')
minimum = pre
for i in range(1,n):
    if d[i-1]=='W':
        pre = pre+1
    if d[i]=='E':
        pre = pre-1
    minimum = min(pre, minimum)

print(minimum)
### BUGGY CODE ###

n = int(input())
listA = list(map(int,input().split()))
count = 0
for k in range(n):
  a = listA[k]
  del listA[k]
  A = set(listA)
  for i in A:
    c = listA.count(i)
    count += int(c*(c-1)/2)
  print(count)
  listA.insert(k,a)
  count = 0


### FIXED CODE ###

from collections import Counter
n = int(input())
su = 0
l = list(map(int,input().split()))
l1 = Counter(l)
for k in l1.values():
  su += k*(k-1)//2
for t in l:
  a = l1[t]
  q = su-a*(a-1)//2+(a-1)*(a-2)//2
  print(q)
### BUGGY CODE ###

n, q = map(int, input().split())
s = str(input())

cum = [0]*n

for i in range(1, len(s)+1):
  sp = s[:i]
  cum[i-1] = sp.count('AC')

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

### FIXED CODE ###

n, q = map(int, input().split())
s = str(input())

cum = [0]*n
current = 0

flag = 0

for i in range(1, len(s)):
  if s[i-1] == 'A' and s[i] =='C':
    current += 1
  cum[i] = current

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

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

def factorized(M):
    d = 2
    f = []
    while d <= M:
        count = 0
        while M % d == 0:
            M //= d
            count += 1
        if count > 0:
            f.append(count)
        d += 1
    return f

def tetra(n, m):
    x = 1
    for y in range(1, n):
        x = x * (m + y - 1) // y
    return x

x = 1
for f in factorized(M):
    x *= tetra(N, f + 1)
    x %= 10 ** 9 + 7

print(x)


### FIXED CODE ###

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

def factorized(M):
    d = 2
    f = []
    while d <= M:
        count = 0
        while M % d == 0:
            M //= d
            count += 1
        if count > 0:
            f.append(count)
        d += 1
        if d < M and d * d > M:
            d = M
    return f

def tetra(n, m):
    x = 1
    for y in range(1, n):
        x = x * (m + y - 1) // y
    return x

x = 1
for f in factorized(M):
    x *= tetra(N, f + 1)
    x %= 10 ** 9 + 7

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

import numpy as np

n, m = map(int, input().split())
edge_l = []
edge_r = []
edge_c = []
for _ in range(m):
  l, r, c = map(int, input().split())
  edge_l.append(l - 1)
  edge_r.append(r - 1)
  edge_c.append(c)
l = np.array(edge_l, dtype=np.int)
r = np.array(edge_r, dtype=np.int)
c = np.array(edge_c, dtype=np.int)

dp = np.ones(n, dtype=np.int) * (c.sum() + 1)
dp[0] = 0
active = np.zeros(n, dtype=np.bool)
active[0] = True
while np.any(active[:-1]):
  act = active.argmax()
  use = (l <= act) * (r > act)
  dp[r[use]] = np.minimum(dp[act] + c[use], dp[r[use]])
  active[r[use]] = True
if active[-1]:
  print(dp[-1])
else:
  print(-1)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
edge = [[]] + [[(0, i)] for i in range(n-1)]
for _ in range(m):
  l, r, c = map(int, input().split())
  edge[l-1].append((c, r-1))

inf = 1 << 60
dp = [0] + [inf] * (n - 1)
queue = [(0, 0)]
check = [False] * n
while queue and not check[-1]:
  dist, act = heapq.heappop(queue)
  check[act] = True
  for cost, vertex in edge[act]:
    if check[vertex]:
      continue
    d = dist + cost
    if dp[vertex] > d:
      heapq.heappush(queue, (d, vertex))
      dp[vertex] = d
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)
### BUGGY CODE ###

import functools
# import math


def solve():
    N = int(input())
    A = [int(i) for i in input().split()]
    # gcd = functools.reduce(math.gcd, A)
    max_gcd = 1
    for i in range(N):
        A_ = A.copy()
        A_.remove(A[i])
        max_gcd = max(max_gcd, functools.reduce(gcd, A_))
    print(max_gcd)


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# 解説を参考に作成
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque

def gcd(a, b):
    """最大公約数"""
    a, b = (a, b) if a >= b else (b, a)
    if b == 0:
        return a
    return gcd(b, a % b)


# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, A):
    L = [0] * N
    L[0] = A[0]
    for i in range(1, N):
        L[i] = gcd(A[i], L[i - 1])
    R = [0] * N
    R[-1] = A[-1]
    for i in range(1, N):
        R[-(i + 1)] = gcd(A[-(i + 1)], R[-i])
    ans = 0
    for i in range(N):
        if i == 0:
            ans = max(ans, R[i + 1])
        elif i == N - 1:
            ans = max(ans, L[i - 1])
        else:
            ans = max(ans, gcd(L[i - 1], R[i + 1]))
    print(ans)


if __name__ == '__main__':
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    # B = [int(i) for i in input().split()]
    # AB = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N, A)

    # # test
    # from random import randint
    # from func import random_str
    # solve()
### BUGGY CODE ###

import numpy as np
import math

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

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

# 1 <= N <= 10^5
# 2 <= M <= 10^9
# 1 <= A <= 10^9

dp = np.zeros(N+1, dtype=int)

dp[N] = 0

total = 0
mods = list()
mods.append(0)

for i in reversed(range(N)):
    for j in range(len(mods)):
        newm = (A[i] + mods[j]) % M
        if newm == 0:
            total += 1
        mods[j] = newm
    mods.append(0)
    # print(mods)
    
print(total)


### FIXED CODE ###

import numpy as np
import math

def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)

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

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

# 1 <= N <= 10^5
# 2 <= M <= 10^9
# 1 <= A <= 10^9

S = []
total = 0
S.append(0)
for i in range(N):
    total = (total + A[i]) % M
    S.append(total)

oS = sorted(S)

count = 0

# print(oS)

cur_val = 0
number = 0
for i in range(0, N+1):
    if oS[i] == cur_val:
        number += 1
    if oS[i] > cur_val or i == N:
        if number >= 2:
            count += int(number * (number - 1) / 2)
        # print(cur_val, number)
        number = 1
        cur_val = oS[i]

print(count)
### BUGGY CODE ###

from collections import Counter


def factorization(n):
    arr = Counter()
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if len(arr.keys()) == 0:
        arr[n] = 1

    return arr


MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
A.sort()

lcm = factorization(A[0])

for a in A:
    b = factorization(a)
    lcm = lcm | b

ans = 0
L = 1
for key in list(lcm.keys()):
    L *= key ** lcm[key]

for a in A:
    ans += L // a
    ans %= MOD

print(ans)


### FIXED CODE ###

from fractions import gcd


MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

lcm = A[0]

for a in A:
    lcm = (lcm * a) // gcd(lcm, a)

ans = 0
for a in A:
    ans += (lcm % MOD) * pow(a, MOD - 2, MOD)
    ans %= MOD

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

S = input()
N = int(input())
flg = 0
L = []
for i in range(N):
    e = input().split()
    if e[0] == '1':
        flg += 1
        flg = flg%2
    else:
        L.append(((flg+int(e[1]))%2, e[2]))

S = ''.join(list(reversed(S))) if flg else S
for f, v in L:
    if (flg+f)%2 == 1:
        S = v + S
    else:
        S = S + v

print(S)

### FIXED CODE ###

S = input()
N = int(input())
flg = 0
L = []
for i in range(N):
    e = input().split()
    if e[0] == '1':
        flg += 1
        flg = flg%2
    else:
        L.append(((flg+int(e[1]))%2, e[2]))

S = ''.join(list(reversed(S))) if flg else S
s1, s2 = '', ''
for f, v in L:
    if (flg+f)%2 == 1:
        s1 += v
    else:
        s2 += v

ans = ''.join(list(reversed(s1))) + S + s2
print(ans)
### BUGGY CODE ###

n = int(input())
strings_list = ["".join(sorted(list(input()))) for i in range(n)]
counter = 0

while True:
    if len(strings_list) == 0 or len(strings_list) == 1:
        break
    else:
        if strings_list[0] not in strings_list[1:]:
            strings_list.pop(0)
        else:
            n = strings_list[1:].count(strings_list[0])
            counter += n * (n + 1) /2
            strings_list = [i for i in strings_list if i != strings_list[0]]
print(round(counter))


### FIXED CODE ###

n = int(input())
strings_list = [list(input()) for i in range(n)]
counter = 0
dict = {}

for strings in strings_list:
    strings = "".join(sorted(strings))
    if strings in dict.keys():
        counter += dict[strings]
        dict[strings] += 1
    else:
        dict[strings] = 1
print(counter)
### BUGGY CODE ###

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

d = int(pow(P, 1/N))+1
for i in range(int(pow(P, 1/N))+1, 0, -1):
  if P % i**N == 0:
    d = i
    break
print(d)

### FIXED CODE ###

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

if N == 1:
  d = P
else:
  d = 1
  i = 2
  while i <= round(pow(P, 1/N)):
    if P % i**N == 0:
      P //= i**N
      d *= i
    else:
      i += 1
print(d)
### BUGGY CODE ###

x, y= map(int, input().split())
mod=10**9+7
import math
a=(2*y-x)//3
b=(2*x-y)//3

if (2*x-y)%3!=0 or (2*y-x)%3!=0 or a<0 or b<0:
	print(0)

else:
	L=[1]*(a+b+1)
	for i in range(1,a+b+1):
		L[i]=L[i-1]*i
		L[i]=L[i]%mod
	ab=L[a]*L[b]
	ab=ab%mod
	for j in range(1, mod):
		abj=(ab*j)%mod
		if abj==L[a+b]:
			print(j)
			break

### FIXED CODE ###

x, y= map(int, input().split())
mod=10**9+7
import math
a=(2*y-x)//3
b=(2*x-y)//3

if (2*x-y)%3!=0 or (2*y-x)%3!=0 or a<0 or b<0:
	print(0)

else:
	L=[1]*(a+b+1)
	for i in range(1,a+b+1):
		L[i]=L[i-1]*i
		L[i]=L[i]%mod
	p=pow(L[a], mod-2, mod)
	q=pow(L[b], mod-2, mod)
	ans=(L[a+b]*p*q)%mod
	print(ans)
### BUGGY CODE ###

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

passwords =[]

a_log=[]
ab_log=[]

for a in range(n-2):
    
    is_a_kaburi = 0
    
    for i in a_log:
        
        if i == s[a]:
            is_a_kaburi = 1
            
    if is_a_kaburi == 0:
        
        a_log.append(a)
        
        for b in range(a+1,n-1):
            
            is_ab_kaburi = 0
            
            for i in ab_log:
                
                if i == s[a]+s[b]:
                    is_ab_kaburi = 1
                    
            if is_ab_kaburi == 0:
                
                ab_log.append(a+b)
    
                for c in range(b+1,n):
                    
                    pw = s[a] + s[b] + s[c] 
                    passwords.append(pw)
                    passwords = list(set(passwords))
                    
                    # print(pw, is_a_kaburi, is_ab_kaburi)

print(len(passwords))

### FIXED CODE ###

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

score = 0

for p in range(1000):
    
    pw = str(p).zfill(3)
    
    start = 0
    n_match = 0
    
    for j in range(3):
        for i in range(start, len(s)):
            
            if s[i] == pw[j]:
                start = i+1
                n_match = n_match+1
                
                if j == 3-1:
                    # print(pw)
                    score = score+1
                
                break
        if n_match <= j:
            break
            
print(score)
### BUGGY CODE ###

#初期入力
import sys
input = sys.stdin.readline
import random
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            ={i:tuple() for i in range(1,N+1)}
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A[i]=a,b             #色を出力するため

#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
color_vertex ={i:set() for i in range(1,N+1)} #頂点に接続している辺に使った色
#color_vertex ={i:[] for i in range(1,N+1)} #頂点に接続している辺に使った色
color_side =[0]*(N-1)
for i in range(N-1):
    v_a,v_b = A[i] #i番目の辺とつながっている頂点
    color =0
    while True:
        q,color =divmod(color,color_max)    #0からcolor_max-1、後で+1
        if color not in color_vertex[v_a] and color not in color_vertex[v_b]:  #使った色リストに入っているか？
            color_side[i] =color+1          #辺の色を出力用に決める（2行上の＋１）
            color_vertex[v_a].add(color)    #前の頂点に使った色として追加
            color_vertex[v_b].add(color)    #先の頂点に使った色として追加
            #color_vertex[v_a].append(color)    #前の頂点に使った色として追加
            #color_vertex[v_b].append(color)    #先の頂点に使った色として追加
            break
        else:
            color +=1
    
#出力
print(color_max)
print(*color_side, sep="\n")

### FIXED CODE ###

"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')
### BUGGY CODE ###

h,w=map(int,input().split())
L=[]
for inp in range(h):
    L.append(input())
#print(L)

#left
grid_l=[]
for y in range(h):
    grid_l.append([])
    n=0
    for x_chr in L[y]:
        if x_chr=="#":
            n=0
        else:
            n+=1
        grid_l[y].append(n)
    
#print(grid_l)

grid_r=[]
for y in range(h):
    grid_r.append([])
    n=0
    for x_chr in L[y][::-1]:
        if x_chr=="#":
            n=0
        else:
            n+=1
        grid_r[y].append(n)
    grid_r[y].reverse()
    
#print(grid_r)

grid_u=[]
for y in range(h):
    grid_u.append([])
for x in range(w):
    n=0
    for y in range(h):
        if L[y][x]=="#":
            n=0
        else:
            n+=1
        grid_u[y].append(n)

#print(grid_u)

grid_d=[]
for y in range(h):
    grid_d.append([])
for x in range(w):
    n=0
    for y in range(h):
        if L[h-y-1][x]=="#":
            n=0
        else:
            n+=1
        grid_d[h-y-1].append(n)

#print(grid_d)

def score(x,y):
    sc=max(grid_l[y][x]+grid_r[y][x]+grid_u[y][x]+grid_d[y][x]-3,0)
    return sc

grid=[]
res=0
for y in range(h):
    for x in range(w):
        res=max(res,score(x,y))
#print(grid)
print(res)
        

### FIXED CODE ###

h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())

tab=[[0 for i in range(w)] for q in range(h)]

cnt=0
for i in range(h):
    cnt=0
    for q in range(w):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for i in range(h):
    cnt=0
    for q in range(w-1,-1,-1):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for q in range(w):
    cnt=0
    for i in range(h):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for q in range(w):
    cnt=0
    for i in range(h-1,-1,-1):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt

print(max([max(col) for col in tab])-3)
### BUGGY CODE ###

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

INF = 1 << 30

# dp初期化
dp = [INF] * n
dp[0] = 0

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

print(dp[n - 1])

### FIXED CODE ###

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

# dp初期化
dp = [float("inf")] * n
dp[0] = 0

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

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

from collections import Counter

def mapdict(itemfunc, dictionary):
    return dict(map(itemfunc, dictionary.items())) 

def minus(tup):
    return (tup[0]-1,tup[1]) 
def plus(tup):
    return (tup[0]+1,tup[1]) 

def count(dic):
    count = 0
    for k,v in dic.items():
        count += abs(k*v)
    return count

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

A2 = [A[i-1]-i for i in range(1,N+1)]
Adic = Counter(A2)

res = count(Adic)
pl = count(mapdict(plus,Adic))
mn = count(mapdict(minus,Adic))

if pl<res:
    tmp = float("inf")
    while res <= tmp:
        tmp = res
        Adic = mapdict(plus, Adic)
        res = count(Adic)
    res = tmp

elif mn<res:
    tmp = float("inf")
    while res <= tmp:
        tmp = res
        Adic = mapdict(minus, Adic)
        res = count(Adic)
    res = tmp

print(res)



### FIXED CODE ###

from collections import Counter

def mapdict(n, dictionary):
    return dict(map(lambda t:(t[0]-n,t[1]), dictionary.items()))

def count(dic):
    count = 0
    for k,v in dic.items():
        count += abs(k*v)
    return count

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

A2 = sorted([A[i-1]-i for i in range(1,N+1)])


Adic = Counter(A2)
Ax  = A2[N//2]
Adic = mapdict(Ax, Adic)

res = count(Adic)

if N==1:
    print(0)

elif N==2:
    print(sum(map(abs,map(lambda x:x-min(A2),A2))))

else:
    pl = count(mapdict(A2[N//2 +1],Adic))
    mn = count(mapdict(A2[N//2 -1],Adic))
    if pl<=res:
        tmp = pl
        tmpc = 1
        while tmp <= res:
            tmpc += 1
            if N//2 + tmpc > N-1:
                break
            res = tmp
            Adic = mapdict(A2[N//2 +tmpc], Adic)
            tmp = count(Adic)
    elif mn<=res:
        tmp = mn
        tmpc = 1
        while tmp <= res:
            tmpc += 1
            if N//2 - tmpc < 0:
                break
            res = tmp
            Adic = mapdict(A2[N//2 -tmpc], Adic)
            tmp = count(Adic)

    print(res)
### BUGGY CODE ###

from bisect import *
N,M,Q=map(int,input().split())
LR=[list(map(int,input().split())) for i in range(M)]
PQ=[list(map(int,input().split())) for i in range(Q)]
data=[[] for i in range(N+1)]
for l,r in LR:
    data[l].append(r)
for i in range(1,N):
    data[i].sort()
for p,q in PQ:
    count=0
    for i in range(p,q+1):
        count+=bisect_right(data[i],q)
    print(count)


### FIXED CODE ###

from bisect import *
N,M,Q=map(int,input().split())
LR=[list(map(int,input().split())) for i in range(M)]
PQ=[list(map(int,input().split())) for i in range(Q)]
data=[[] for i in range(N+1)]
for l,r in LR:
    data[l].append(r)
for i in range(1,N):
    data[i].sort()

data2=[[0] for i in range(N+1)]
for i in range(1,N+1):
    for c in range(1,N+1):
        data2[i].append(bisect_right(data[i],c))
#print(data2)
for p,q in PQ:
    count=0
    for i in range(p,q+1):
        count+=data2[i][q]
    print(count)
### BUGGY CODE ###

N, M=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
if N==1:
  print(A[0]//(2**M))
else:
  while M>0:
    while M>0 and A[-1]>=A[-2]:
      A[-1]=A[-1]//2
      M-=1
    A.sort()
  print(sum(A))

### FIXED CODE ###

import heapq
N, M=map(int, input().split())
A=list(map(int, input().split()))
A=list(map(lambda x: -x, A))
heapq.heapify(A)
for i in range(M):
  heapq.heappush(A, (heapq.heappop(A)+1)//2)
print(-sum(A))