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

import sys
# import pdb
input = sys.stdin.readline

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

dp_list = [-1 for _ in range(N)]
dp_list[0] = 0
dp_list[1] = abs(hs[1] - hs[0])

sys.setrecursionlimit(1000000)
def dp_memo(p):
  if dp_list[p] != -1:
    return dp_list[p]

  costs = []
  if K <= p:
    for i in range(1,K+1):
        costs.append(dp_memo(p-i) + abs(hs[p] - hs[p-i]))
  else:
    for i in range(1,p+1):
        costs.append(dp_memo(p-i) + abs(hs[p] - hs[p-i]))
  result = min(costs)
  dp_list[p] = result
  return result


def dp_recur():
  cost1 = 0
  cost2 = abs(hs[1] - hs[0])

  if N == 2:
    print(cost2)
    exit()
  # pdb.set_trace()
  for i in range(2, N):
    cost3 = min(cost2 + abs(hs[i] - hs[i-1]), cost1 + abs(hs[i] - hs[i-2]))
    cost1 = cost2
    cost2 = cost3
  return cost3

# print(dp_recur())
print(dp_memo(N-1))


### FIXED CODE ###

import sys
# import pdb
input = sys.stdin.readline

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

inf = 1e10

dp_list = [inf for _ in range(N)]
dp_list[0] = 0

# import heapq

sys.setrecursionlimit(1000000)
def dp_memo(p):
  if dp_list[p] != -1:
    return dp_list[p]

  costs = []
  # heapq.heapify(costs)
  if K <= p:
    for i in range(1,K+1):
        # heapq.heappush(costs, dp_memo(p-i) + abs(hs[p] - hs[p-i]))
        costs.append(dp_memo(p-i) + abs(hs[p] - hs[p-i]))
  else:
    for i in range(1,p+1):
        # heapq.heappush(costs, dp_memo(p-i) + abs(hs[p] - hs[p-i]))
        costs.append(dp_memo(p-i) + abs(hs[p] - hs[p-i]))
  result = min(costs)
  # result = heapq.heappop(costs)
  dp_list[p] = result
  return result


def dp_recur(N):
  for i in range(1, N):
    for j in range(1,K+1):
      if i-j < 0:
        break
      dp_list[i] = min(dp_list[i], dp_list[i-j] + abs(hs[i] - hs[i-j]))
  return dp_list[N-1]

print(dp_recur(N))
# print(dp_memo(N-1))
### BUGGY CODE ###

A,B,C,K = map(int,input().split())

s=-1*K*C

lc=[]
lc_=[]
for i in range(K+1):
  for j in range(K-i+1):
    lc.append([i,j,K-i-j])

#print(lc)

for i in range(len(lc)):
  if lc[i][0]<=A and lc[i][1]<=B and lc[i][2]<=C:
    # print(lc[i])
    s=max(s, lc[i][0]-lc[i][2])

print(s)


### FIXED CODE ###

A,B,C,K = map(int,input().split())

if A+B<K:
  print(A-(K-A-B))
else:
  print(min(A, K))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b,count = [],0
for i in range(0,n,1):
    b.append(a[i])
    if(a[i] == min(b)):
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b,count = [],0
mv = a[0]
for i in range(0,n,1):
    b.append(a[i])
    if(a[i] <= mv):
        count += 1
        mv = a[i]
print(count)
### BUGGY CODE ###

import sys,math

N,A,B=map(int,input().split())
H = [0] * N
H = [int(input()) for i in range(N)]

L=-1
R=sys.maxsize

def binary_search(D,U):
    MID=(D+U)//2
    if(MID==D):
        print(U)
    else:
        if sum(math.ceil(max(h-B*MID,0)/(A-B))for h in H)<=MID:
            binary_search(D,MID)
        else:
            binary_search(MID,U)


binary_search(L,R)


   


### FIXED CODE ###

import math

N,A,B=map(int,input().split())
H = [0] * N
H = [int(input()) for i in range(N)]

maxH = max(H)
L=-1
R=math.ceil(maxH / B)

def binary_search(D,U):
    MID=(D+U)//2
    if(MID==D):
        print(U)
    else:
        if sum(math.ceil(max(h-B*MID,0)/(A-B))for h in H)<=MID:
            binary_search(D,MID)
        else:
            binary_search(MID,U)


binary_search(L,R)
### BUGGY CODE ###

s = list(input())
k = int(input())
sub = []
for i in range(1, len(s) + 1):
    for j in range(1, len(s) + 2 - i):
        if not([s[s_i - 1] for s_i in range(j, j + i)] in sub):
            sub.append([s[s_i - 1] for s_i in range(j, j + i)])
sub.sort()
print(''.join(sub[k-1]))


### FIXED CODE ###

s = list(input())
k = int(input())
sub = []
for i in range(1, min(len(s) + 1, k + 1)):
    for j in range(1, len(s) + 2 - i):
        if not([s[s_i - 1] for s_i in range(j, j + i)] in sub):
            sub.append([s[s_i - 1] for s_i in range(j, j + i)])
sub.sort()
print(''.join(sub[k-1]))
### BUGGY CODE ###

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

mod=10**9+7
sum=0
for i in range(N-1):
    for j in range(i+1,N):
        sum+=((A[i])*(A[j] ))
        sum=sum%mod
print(sum)

### FIXED CODE ###

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

mod=10**9+7

B=[0]
for i in range(1,N+1):
    B.append(A[i-1]+B[i-1])

ans=0
for i in range(N-1):
    ans+=A[i]*(B[N]-B[i+1])
    ans%=mod

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

n,k = map(int , input().split())
sum = 0
a = list(map(int , input().split()))
tmp = 1
for i in range(0,k):
    tmp *= a[i]
for i in range(k,n):
    # print(tmp)
    if tmp*a[i]/a[i-k] > tmp:
        print("Yes")
    else:
        print("No")
    tmp = tmp*a[i]/a[i-k]

### FIXED CODE ###

n,k = map(int , input().split())
sum = 0
a = list(map(int , input().split()))
for i in range(k,n):
    if a[i] > a[i-k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

line = input().split(sep=" ")
x = int(line[0])
y = int(line[1])
z = int(line[2])
in_k = int(line[3])


in_x = list(map(int,input().split(sep=" ")))
in_y = list(map(int,input().split(sep=" ")))
in_z = list(map(int,input().split(sep=" ")))

ans_arr = []

for i in range(x):
	for j in range(y):
		for k in range(z):
			ans_arr.append(in_x[i] + in_y[j] + in_z[k])

ans_arr = sorted(ans_arr,reverse=True)

for i in range(in_k):
	print(ans_arr[i])


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())

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


A = sorted(A, key = lambda x:-x)
B = sorted(B, key = lambda x:-x)
C = sorted(C, key = lambda x:-x)

AB = [0] * (X * Y)

ABC = []

for i in range(X):
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for k in range(Z):
            if (i + 1) * (j + 1) * (k + 1) > K:
                break
            ABC.append(A[i] + B[j] + C[k])

ABC = sorted(ABC, key = lambda x:-x)
for i in range(0, K):
    print(ABC[i])
### BUGGY CODE ###

H, W = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
Diff = [[False] * (W + 1) for _ in range(H + 1)]
M = 0
for i in range(H):
    for j in range(W):
        m = abs(A[i][j] - B[i][j])
        Diff[i][j] = m
        M += m

dp = [[[0] * (M + 1) for _ in range(W + 1)] for _ in range(H + 1)]
dp[0][0][Diff[0][0]] = 1

for i in range(0, H):
    for j in range(0, W):
        for k in range(M + 1):
            if dp[i][j][k]:
                dp[i + 1][j][k + Diff[i + 1][j]] |= True
                dp[i + 1][j][abs(k - Diff[i + 1][j])] |= True
                dp[i][j + 1][k + Diff[i][j + 1]] |= True
                dp[i][j + 1][abs(k - Diff[i][j + 1])] |= True

for k in range(M + 1):
    if dp[H - 1][W - 1][k] == 1:
        ans = k
        break

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
Diff = [[0] * (W + 1) for _ in range(H + 1)]
M = 0
for i in range(H):
    for j in range(W):
        m = abs(A[i][j] - B[i][j])
        Diff[i][j] = m
        M += m

dp = [[0] * (W + 1) for _ in range(H + 1)]
dp[0][0] |= (1 << Diff[i][j])

for i in range(0, H):
    for j in range(0, W):
        here = dp[i][j]
        s = Diff[i][j]
        ni = 0
        nj = 0
        ni |= (here << s)
        nj |= (here << s)
        ni |= (here >> s)
        nj |= (here >> s)
        ex = 0
        for k in range(1, s + 1):
            if (here >> k) & 1:
                ex |= (1 << (s - k))
        ni |= ex
        nj |= ex
        dp[i + 1][j] |= ni
        dp[i][j + 1] |= nj

a = dp[H - 1][W - 1]
ans = 0
for k in range(M + 1):
    if (a >> k) & 1:
        ans = k
        break

print(k)
### BUGGY CODE ###

import sys


def main():
    input = sys.stdin.readline

    r, c, k = map(int, input().split())

    items = [[0] * (c + 1) for _ in range(r + 1)]
    for _ in range(k):
        i, j, v = map(int, input().split())
        items[i][j] = v

    # dp[i][j][m] = (i行j列時点で、i行でm個のitemを取得している時の価値の最大値)
    dp = [[[0] * 4 for _ in range(c + 1)] for _ in range(r + 1)]

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            for m in range(4):
                dp[i][j][m] = max(dp[i - 1][j][3], dp[i][j - 1][m])
            if items[i][j] > 0:
                for m in [2, 1, 0]:
                    dp[i][j][m + 1] = max(dp[i][j][m + 1],
                                          dp[i][j][m] + items[i][j])

    print(dp[r][c][3])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline

    r, c, k = map(int, input().split())

    items = [[0] * (c + 1) for _ in range(r + 1)]
    for _ in range(k):
        i, j, v = map(int, input().split())
        items[i][j] = v

    # dp[m][i][j] = (i行j列時点で、i行でm個のitemを取得している時の価値の最大値)
    dp = [[[0] * (c + 1) for _ in range(r + 1)] for _ in range(4)]

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            for m in range(4):
                dp[m][i][j] = max(dp[3][i - 1][j], dp[m][i][j - 1])
            if items[i][j] > 0:
                for m in [2, 1, 0]:
                    dp[m + 1][i][j] = max(dp[m + 1][i][j],
                                          dp[m][i][j] + items[i][j])

    print(dp[3][r][c])


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

X,Y = map(int,input().split())
i = 1
if X == Y:
    print(-1)
    exit()
while True:
    if X * i % Y != 0:
        break
    if X * i > 10**18:
        print(-1)
        exit()
    i += 1
print(X * i)

### FIXED CODE ###

X,Y = map(int,input().split())
i = 1
if X % Y == 0:
    print(-1)
    exit()
while True:
    if X * i % Y != 0:
        break
    if X * i > 10**18:
        print(-1)
        exit()
    i += 1
print(X * i)
### BUGGY CODE ###

N, K = map(int, input().split())
p = [int(x) for x in input().split()]

p_sum = 0
n = 0
for i in range(N-K+1):
 if p_sum < sum(p[i:i+K]):
   p_sum = sum(p[i:i+K])
   n = i

def allsum(x):
  return x * (x+1) // 2

ans = 0
for j in range(K):
  ans += allsum(p[n+j]) / p[n+j]
print(ans)

### FIXED CODE ###

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

a = 0
for i in range(N - K + 1):
  if i == 0:
    b = sum(p[0:K])
  else:
    b = b - p[i-1] + p[i + K - 1]
  
  if b > a:
    a = b
    f = i

ans = 0
for j in range(K):
  ans += (p[f + j] + 1) / 2

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

L, R = [int(i) for i in input().split()]
min_mod = (L * R) % 2019 
for i in range(L, R):
    for j in range(i+1,R+1):
        if min_mod > (i * j) % 2019:
            min_mod =(i * j) % 2019
            if min_mod == 0:
                break
print(min_mod)

### FIXED CODE ###

L, R = [int(i) for i in input().split()]
min_mod = (L * R) % 2019 

if R - L > 2019:
    min_mod = 0
else :
    for i in range(L, R):
        for j in range(i+1,R+1):
            if min_mod > (i * j) % 2019:
                min_mod =(i * j) % 2019
                if min_mod == 0:
                    break
print(min_mod)
### BUGGY CODE ###

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

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

INF = 1e12

dp = [INF] * n
dp[0] = 0
dp[1] = abs(pedras[1] - pedras[0])

for i in range(n):#i == pedra atual
    for j in range(i+1, i + k+ 1):
        if j < n:
            dp[j] = min(dp[j], dp[i] + abs(pedras[i] - pedras[j]))

print(dp[n-1])


### FIXED CODE ###

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

INF = 1e12

dp = [INF] * n

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

dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2,n):#Ele vai começar a contar cada pedra a partir da terceira
    pulo = 0
    for j in range(i-1,-1,-1):#O pulo começar pequeno, tendo tamanho 1 e indo até o máximo k
        pulo += 1
        if pulo > k:
            break
        else:
            dp[i] = min(dp[i], dp[j] + abs(h[j] - h[i]))
#No final ele vai armazenar o pulo de menor custo, afinal não importa o tamanho do pulo e sim seu custo, sendo assim,
#Temos que calcular os custos de todos os possiveis pulos até a pedra atual.

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

s = input()
q = int(input())
import math
jun = 1
for _ in range(q):
  
  tmp = input()
  if len(tmp)==1:
    jun = math.ceil(jun*(-1/2)+1/2)
  else:
    _,f,c = tmp.split()
    f = int(f)
    if jun+f ==2:
      s = c+s
    else:
      s += c
if jun==1:
  print(s)
else:
  print(s[::-1])
      
    


### FIXED CODE ###

s = input()
q = int(input())
jun = 1
f = "";t = ""
for _ in range(q):
  
  tmp = input()
  if len(tmp)==1:
    jun = 1 if jun==0 else 0 
  else:
    _,ff,c = tmp.split()
    if jun+int(ff) ==2:
      f = c+f
    else:
      t += c
if jun==1:
  print(f+s+t)
else:
  print((f+s+t)[::-1])
### BUGGY CODE ###

H, W, M = map(int, input().split())
bombs = [list(map(lambda x:int(x) - 1, input().split())) for _ in range(M)]

max_hw = max(H, W)
H_count = {i:0 for i in range(max_hw)}
W_count = {i:0 for i in range(max_hw)}

for i in range(M):
    h, w = bombs[i]
    H_count[h] += 1
    W_count[w] += 1


A = max(H_count.values())
B = max(W_count.values())
Ah = []
Bw = []

for i in range(max_hw):
    h, count_h = i, H_count[i]
    w, count_w = i, W_count[i]

    if count_h == A:
        Ah.append(h)
    if count_w == B:
        Bw.append(w)

ans = A + B
FLG = True
for h in Ah:
    for w in Bw:
        if [h, w] not in bombs:
            FLG = False
            break
    if not FLG:
        break

print(ans - FLG)


### FIXED CODE ###

H, W, M = map(int, input().split())
bombs = set()

H_count = [0 for i in range(H)]
W_count = [0 for i in range(W)]

for i in range(M):
    h, w = map(lambda x:int(x) - 1, input().split())
    bombs.add((h, w))
    H_count[h] += 1
    W_count[w] += 1


A = max(H_count)
B = max(W_count)
Ah = []
Bw = []

for i, count in enumerate(H_count):
    if count == A:
        Ah.append(i)

for i, count in enumerate(W_count):
    if count == B:
        Bw.append(i)

ans = A + B
for h in Ah:
    for w in Bw:
        if (h, w) not in bombs:
            print(ans)
            exit()

print(ans - 1)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [readline().strip() for j in range(H)]

    white = []
    for line in S:
        white.append(line.count("1"))
    white_total = sum(white)

    if white_total <= K:
        print(0)
        exit()

    ans = 10**5
    for i in range(2**(H-1)):
        impossible = False
        x = 0
        ly = bin(i).count("1")
        y_sum = [0]*(ly + 1)
        j = 0
        while j < W:
            m = 0
            y = [0]*(ly + 1)
            for k, s in enumerate(S):
                if s[j] == "1":
                    y[m] += 1
                    if y[m] > K:
                        impossible = True
                        break
                    y_sum[m] += 1
                    if y_sum[m] > K:
                        x += 1
                        y_sum = [0]*(ly + 1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1
            if impossible:
                x = 10**6
                break

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [readline().strip() for j in range(H)]

    white = []
    for line in S:
        white.append(line.count("1"))
    white_total = sum(white)

    if white_total <= K:
        print(0)
        exit()

    ans = 10**5
    for i in range(2**(H-1)):
        impossible = False
        x = 0
        ly = bin(i).count("1")
        y_sum = [0]*(ly + 1)
        j = 0
        while j < W:
            m = 0
            y = [0]*(ly + 1)
            for k in range(H):
                if S[k][j] == "1":
                    y[m] += 1
                    if y[m] > K:
                        impossible = True
                        break
                    y_sum[m] += 1
                    if y_sum[m] > K:
                        x += 1
                        y_sum = [0]*(ly + 1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1
            if impossible:
                x = 10**6
                break

        ans = min(ans, x + ly)

    print(ans)


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

import sys

INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10 ** 9)


def main():
    N, Q = MAP()
    S = INPUT()
    ans = []

    for i in range(Q):
        l, r = MAP()

        cnt = 0
        for j in range(l, r):
            if S[j-1:j+1] == "AC": cnt += 1

        ans.append(cnt)

    print(*ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())

sys.setrecursionlimit(10 ** 9)


def main():
    N, Q = MAP()
    S = INPUT()
    
    L = [0]
    for i in range(N-1):
        L.append(L[-1] + (1 if S[i:i+2] == "AC" else 0))

    ans = []
    for i in range(Q):
        l, r = MAP()
        ans.append(L[r-1] - L[l-1])

    print(*ans)


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

N,X,Y=map(int,input().split())
def dist(i,j):
  return min([j-i,abs(X-1-i)+1+abs(Y-1-j),abs(Y-1-i)+1+abs(X-1-j)])
dists = []
for i in range(N-1):
  for j in range(i+1,N):
    dists.append(dist(i,j))
for i in range(1,N):
  print(len([str(v) for v in dists if v == i]))
  
    

### FIXED CODE ###

N,X,Y=map(int,input().split())
def dist(i,j):
  return min([j-i,abs(X-1-i)+1+abs(Y-1-j),abs(Y-1-i)+1+abs(X-1-j)])
dists = {v:0 for v in range(1,N)}
for i in range(N-1):
  for j in range(i+1,N):
    d = dist(i,j)
    dists[d]+=1
for i in range(1,N):
  print(dists[i])
### BUGGY CODE ###

n=int(input())
s=input()
cnt=0
if n<=3:
    print(0)
    quit()
for i in range(n-2):
    si=s[i]
    for j in range(i+1,n-1):
        sj=s[j]
        if si!=sj:
            for k in range(j+1,n):
                sk=s[k]
                if sk!=si and sk!=sj and j-i!=k-j:
                    cnt+=1
print(cnt)
            


### FIXED CODE ###

n = int(input())
s =     input()
if n < 3:
  print(0)
  exit

result = s.count('R') * s.count('G') * s.count('B')
for i in range(n):
  for j in range(i+1, n):
    k = 2*j - i
    if k < n and s[k] != s[i] and s[k] != s[j] and s[j] != s[i]:
      result -= 1

print(result)
### BUGGY CODE ###

A,B=map(int,input().split())
lst=set()
i=2
while i<=A and i<=B:
    #print(i,A,B,lst)
    if A%i==0 and B%i==0:
        flag=1
        for l in lst:
            if i%l==0:
                flag=0
                break

        if flag:
            lst.add(i)
        while A%i==0:
            A=A//i
        while B%i==0:
            B=B//i    
    i+=1


lst.add(1)
#print(lst)
print(len(lst))


### FIXED CODE ###

A,B=map(int,input().split())
lst=set()
def factorization(n):
    arr = []
    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.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

if A==B==1:
    print(1)
else:
    print(len(set([i[0] for i in factorization(A)])&set([i[0] for i in factorization(B)]))+1)
### BUGGY CODE ###

from numba import njit, jit, int32
import numpy as np
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
# p = list(map(int, input().split()))
p = np.array(input().split(), dtype=np.int32)


@njit('(i4,i4[::1])', cache=True)
def main(n, p):
#     d = [[None]*n for _ in range(n)]
    d = np.zeros((n,n), dtype=np.int32)
    for i in range(n):
        for j in range(n):
            d[i,j] = min(i, n-1-i, j, n-1-j)
#     vacant = [[False]*n for _ in range(n)]
    vacant = np.zeros((n,n), dtype=np.int32)

    ans = 0
    for v in p:
        v -= 1
        x,y = v//n, v%n
        ans += d[x,y]
    #     print(v, d[x][y], d)
        v = d[x,y]
        q = [(v, x, y)]
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        while q:
            v,i,j = q.pop()
            for xx, yy in zip(dx,dy):
                ii = i+xx
                jj = j+yy
                if ii<0 or jj<0 or ii>=n or jj>=n:
                    continue
                if d[ii,jj]>v:
                    d[ii,jj] = v
                    nv = v+1 if not vacant[ii,jj] else v
                    q.append((nv, ii, jj))

        vacant[x,y] = 1
    return ans
ans = main(n,p)
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)