Harryxun/stf_run huggingface dataset:
N, M, *L = map(int, open(0).read().split())
dic = defaultdict(list)
rdic = defaultdict(list)
nin = [0]*N
Els = []
for a,b,c in zip(*[iter(L)]*3):
  dic[a-1] += [b-1]
  rdic[b-1] += [a-1]
  nin[b-1] += 1
  Els += [(a-1,b-1,-c)]

To = [False]*N
From = [False]*N
q = [0]
To[0] = True
while q:
  p = q.pop()
  for e in dic[p]:
    if To[e]==False:
      To[e] = True
      q += [e]
q = [N-1]
From[N-1] = True
while q:
  p = q.pop()
  for e in rdic[p]:
    if From[e]==False:
      From[e] = True
      q += [e]

ok = [False]*N
for i  in range(N):
  ok[i] = To[i]&From[i]

cnt = 0
dist = [float('inf')]*N
dist[0] = 0
cnt = 0
flag = False
while True:
  update = True
  for a,b,c in Els:
    if not(ok[a] and ok[b]):
      continue
    if dist[a]!=float('inf') and dist[b]>dist[a]+c:
      dist[b] = dist[a]+c
      update = False
  if update:
    break
  cnt += 1
  if cnt>N:
    flag = True
    break

if flag:
  print('inf')
else:
  print(-dist[N-1])

### FIXED CODE ###

from collections import defaultdict
N, M, *L = map(int, open(0).read().split())
dic = defaultdict(list)
rdic = defaultdict(list)
nin = [0]*N
Els = []
for a,b,c in zip(*[iter(L)]*3):
  dic[a-1] += [b-1]
  rdic[b-1] += [a-1]
  nin[b-1] += 1
  Els += [(a-1,b-1,-c)]

To = [False]*N
From = [False]*N
q = [0]
To[0] = True
while q:
  p = q.pop()
  for e in dic[p]:
    if To[e]==False:
      To[e] = True
      q += [e]
q = [N-1]
From[N-1] = True
while q:
  p = q.pop()
  for e in rdic[p]:
    if From[e]==False:
      From[e] = True
      q += [e]

ok = [False]*N
for i  in range(N):
  ok[i] = To[i]&From[i]

cnt = 0
dist = [float('inf')]*N
dist[0] = 0
cnt = 0
flag = False
while True:
  update = True
  for a,b,c in Els:
    if not(ok[a] and ok[b]):
      continue
    if dist[a]!=float('inf') and dist[b]>dist[a]+c:
      dist[b] = dist[a]+c
      update = False
  if update:
    break
  cnt += 1
  if cnt>2*N:
    flag = True
    break

if flag:
  print('inf')
elif dist[N-1]==float('inf'):
  print('inf')
else:
  print(-dist[N-1])
import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(sys.stdin.readline())
left = list(map(int, sys.stdin.read().split()))
assert len(left) == N
assert left[0] == 0

counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())


### FIXED CODE ###

import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(sys.stdin.readline())
left = list(map(int, sys.stdin.read().split()))
counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    if sum(h) != N:
        return 0
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())
l, r, d = map(int, input().split())
c = 0
for i in range(l,r+1):
  if i % d = 0:
    c += 1
print(c)

### FIXED CODE ###

l, r, d = map(int, input().split())
c = 0
for i in range(l,r+1):
  if i % d == 0:
    c += 1
print(c)
def mizuyari2(l):
    count = 0
    stopper = 0

    for i in l:
        stopper+=i 
    if(stopper == 0):
        return 0        

    if(l[0]!=0):
        count+=1
    for i in range(len(l)-1):
        if(l[i]==0 and l[i+1]!=0):
            count+=1
    if(l[len(l)-2]==0 and l[len(l)-1!=0]):
        count+=1

    for index,i in enumerate(l):           
        l[index]-=1
        if(l[index]<0):
            l[index]=0

    return count+mizuyari2(l)

N = int(input())
h = []

for i in range(N):
    h.append(int(input()))

print(mizuyari2(h))

### FIXED CODE ###

import array
def count_mizuyari(l):
    count = 0
    arr = array.array('i',[0])
    arr.extend(l)
    for i in range(len(arr)-1):
        if(arr[i]==0 and arr[i+1]!=0):
            count += 1
    return count
    

def mizuyari2(l):
    count = 0
    stopper = 0

    #要素が全部0かどうかの判定
    for i in l:
        stopper+=i 
    if(stopper == 0):
        return 0 
    else:     
        count=count_mizuyari(l)
    for index,i in enumerate(l):           
        l[index]-=1
        if(l[index]<0):
            l[index]=0

    return count+mizuyari2(l)

N = int(input())
h = array.array('i')

li = input().rstrip().split()
for i in li:
    h.append(int(i))


print(mizuyari2(h))
from math import gcd
def f(x):
    return x%2==0 or x%3==0 or x%5==0

prd = list(filter(lambda x: f(x[0]) and f(x[1]), [(i, 30 - i) for i in range(1, 14)]))

pairs = []
for i in range(1, 1000):
    for j in prd:
        pairs += [i * 30 + j[0], i * 30 + j[1]]
for i in range(0, 500):
    pairs += [i * 30 + 15, (999 - i) * 30 + 15]
pairs += [4, 26, 6, 24, 8, 22, 9, 21, 10, 20, 12, 18, 14, 16]
N = int(input())
if N == 4:
    print(2, 3, 25, 30)
    exit(0)

a = [2, 3, 25]
aiv = [28, 27, 5]
if (N - len(a)) % 2 == 1: a += aiv

a += pairs
for i in range(1, 1001): a.append(i * 30)
print(" ".join(map(str, a[:N])))


### FIXED CODE ###

def f(x):
    return x%2==0 or x%3==0 or x%5==0

prd = list(filter(lambda x: f(x[0]) and f(x[1]), [(i, 30 - i) for i in range(1, 14)]))

pairs = []
for i in range(1, 1000):
    for j in prd:
        pairs += [i * 30 + j[0], i * 30 + j[1]]
for i in range(0, 500):
    pairs += [i * 30 + 15, (999 - i) * 30 + 15]
pairs += [4, 26, 6, 24, 8, 22, 9, 21, 10, 20, 12, 18, 14, 16]
N = int(input())
if N == 4:
    print(2, 3, 25, 30)
    exit(0)

a = [2, 3, 25]
aiv = [28, 27, 5]
if (N - len(a)) % 2 == 1: a += aiv

a += pairs
for i in range(1, 1001): a.append(i * 30)
print(" ".join(map(str, a[:N])))
N = int(input())
for i in range(N):
    cord_list.append(list(map(int, input().split())))

cord_list = [[0, 0, 0]]
flag = 0

for j in range(N):
    a = cord_list[j+1][0] - cord_list[j][0]
    b = abs(cord_list[j+1][1] - cord_list[j][1])
    c = abs(cord_list[j+1][2] - cord_list[j][2])
    if ((a - (b + c))%2 ==0) & ((b+c) <= a):
        pass
    else:
        print("No")
        flag += 1
        break
        
if flag == 0:
    print("Yes")

### FIXED CODE ###

N = int(input())
cord_list = [[0, 0, 0]]
flag = 0
for i in range(N):
    cord_list.append(list(map(int, input().split())))
    
for j in range(N):
    a = cord_list[j+1][0] - cord_list[j][0]
    b = cord_list[j+1][1] - cord_list[j][1]
    c = cord_list[j+1][2] - cord_list[j][2]
    if ((a - (abs(b) + abs(c)))%2 ==0) & ((abs(b) + abs(c)) <= a):
        pass
    else:
        print("No")
        flag += 1
        break
        
if flag == 0:
    print("Yes")
S = input().split()
A = int(S[0])
B = float(S[1])

from mpmath import mp
mp.dps = 50

res = mp.mpf(B*A)
print(int(res))

### FIXED CODE ###

from decimal import *

a, b = input().split()
x = Decimal(a)
y = Decimal(b)

print(int(x*y))
input_len = input()
ans = 1
for i in range(1, input_len+1):
    ans *= i

ans = ans % (10 ** 9) + 7
print(ans)

### FIXED CODE ###

input_len = int(input())
ans = 1
for i in range(1, input_len+1):
    ans = (i * ans) % (10 ** 9 + 7)

print(ans)
def brute_force(s, K):
    substring_set = set()

    # brute-force
    for start in range(len(s)):
        # 5まででよかった...
        for length in range(1, 6):
            substring = s[start:start+length]
            substring_set.add(substring)

    substring_list = sorted(list(substring_set))
    print(substring_list)
    print(substring_list[K - 1])

brute_force(s, K)

### FIXED CODE ###

s = input()
K = int(input())


def brute_force(s, K):
    substring_set = set()

    # brute-force
    for start in range(len(s)):
        # 5まででよかった...
        for length in range(1, 6):
            substring = s[start:start+length]
            substring_set.add(substring)

    substring_list = sorted(list(substring_set))
    print(substring_list[K - 1])

brute_force(s, K)
K=int(input())
i=0
current_num=0
while (i<K) :
  current_string=str(current_num)
  flag=True
  for k in range(len(current_string)-1) :
    if abs(int(current_string[k])-int(current_string[k+1]))>1 :
      flag=False
      break
  if flag=True :
    i+=1
  current_num+=1
  
print(current_num)


### FIXED CODE ###

from collections import deque
a=int(input())
list1=deque([1,2,3,4,5,6,7,8,9])
i=1
while(i<=a) :
  #print (list1)
  if i!=a :
    k=list1.popleft()
    k=str(k)
    if int(k[-1])==0 :
      list1.append(int(str(k)+'0'))
      list1.append(int(str(k)+'1'))
      i+=1
    elif int(k[-1])==9 :
      list1.append(int(str(k)+'8'))
      list1.append(int(str(k)+'9'))
      i+=1
    else :
      list1.append(int(str(k)+str(int(k[-1])-1)))
      list1.append(int(str(k)+str(int(k[-1]))))
      list1.append(int(str(k)+str(int(k[-1])+1)))
      i+=1
  else :
    print(list1[0])
    break
a=input()
if a=='SUN':
  print(7)
elif a=='MON':
  print(6)
elif a=='TUE':
  print(5)
elif a=='WED':
  pirnt(4)
elif a=='THU':
  print(3)
elif a=='FRI':
  print(2)
elif a=='SAT':
  print(1)


### FIXED CODE ###

c=0
a=input()
if a=='SUN':
  c+=7
elif a=='MON':
  c+=6
elif a=='TUE':
  c+=5
elif a=='WED':
  c+=4
elif a=='THU':
  c+=3
elif a=='FRI':
  c+=2
else:
  c+=1
print(c)
from statistics import mean
import math

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

mean_num = mean(A)
Ceil = math.ceil(mean_num)
Floor = math.floor(mean_num)

Ceil_sum = 0
Floor_sum = 0
for i in A:
    Ceil_sum += (Ceil - i) ** 2
for i in A:
    Floor_sum += (Floor - i) ** 2

print(min(Floor_sum, Ceil_sum))

### FIXED CODE ###

from statistics import mean
import math

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

mean_num = mean(A)
Ceil = math.ceil(mean_num)
Floor = math.floor(mean_num)

Ceil_sum = 0
Floor_sum = 0
for i in A:
    Ceil_sum += (Ceil - i) ** 2
for i in A:
    Floor_sum += (Floor - i) ** 2

print(min(Floor_sum, Ceil_sum))
n,x=map(int,input().split())
l=list(map(int,input().split()))

d=0
for i in range(n+1):
    if d>x:
        break
    d=d+l[i]

print(i)


### FIXED CODE ###

n,x=map(int,input().split())
l=list(map(int,input().split()))

d=0
for i in range(n+1):
    if (i>n-1)and(d<=x):
        i+=1
        break
    if d>x:
        break
    d=d+l[i]

print(i)
S = list(input())
K = int(input())
x = set()

for i in range(len(S)):
    for j in range(1,min(len(S) - i + 1, K + 1)):
        x.add(S[i:i + j])

x = list(x)
x.sort()
print(x[K - 1])

### FIXED CODE ###

S = input()
K = int(input())
x = set()

for i in range(len(S)):
    for j in range(1,min(len(S) - i + 1, K + 1)):
        x.add(S[i:i + j])

x = list(x)
x.sort()
print(x[K - 1])
import numpy as np
a = int(input())
b = np.array(list(map(int, input().split())))
b = np.prod(b)
if b >= 10**18:
    print(-1)
else:print(b)

### FIXED CODE ###

a, b = map(int, input().split())
print(a*b)
import statistics
n=int(input())
box=list(map(int,input().split()))
box_another=sorted(list(y-(x+1) for x,y in enumerate(box)))
median=int(statistics.median(box_another))
count=0
for x,y in enumerate(box):
    count +=abs(y-(x+1+median))
print(count)

### FIXED CODE ###

import statistics
n=int(input())
box=list(map(int,input().split()))
box_another=sorted(list(y-(x+1) for x,y in enumerate(box)))
median=int(statistics.median(box_another))
count=0
for x,y in enumerate(box):
    count +=abs(y-(x+1+median))
print(count)
import math
a,b,c,d=map(int,input().split())
num1=(b//c)-(-1*(a//-c))+1
num2=(b//d)-(-1*(a//-d))+1
num=c*d//(math.gcd(c,d))
num3=(b//num)-(-1*(a//-num))+1
print(b-a+1-num1-num2+num3)


### FIXED CODE ###

import fractions
a,b,c,d=map(int,input().split())
num1=(b//c)-(-1*(a//-c))+1
num2=(b//d)-(-1*(a//-d))+1
num=c*d//(fractions.gcd(c,d))
num3=(b//num)-(-1*(a//-num))+1
print(b-a+1-num1-num2+num3)
n,k=map(int,input().split())
l=list(map(int,input().split()))
a=0
l.sort(reverse=True)
for i in range(k):
    a+=l[i]
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
a=0
l.sort(reverse=True)
for i in range(k):
    a+=l[i]
print(a)
# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# from bisect import bisect_left
from heapq import heapify,heappush,heappop
# from numba import njit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np    # numpy.lcm()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk
# import networkx as nx
# G = Graph()

# slist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())

def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

if N == 1:
    print(0)
    exit()

ans = 0
_ , Zque = primes(N)
Zset = set(Zque)
Z = heappop(Zque)
if N in Zque:
    print(1)
    exit()

while N >= Z:
    # print(N,Z)
    if N%Z == 0:
        ans += 1
        N = N//Z
    i = Z
    num = Z
    j = 2
    while num <= N:
        # print("num=",num,"N=",N,"j=",j)
        if not num in Zset:
            heappush(Zque,num)
            Zset.add(num)
        num = i**j
        j += 1
    Z = heappop(Zque)

print(ans)
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
from collections import deque,Counter
# from bisect import bisect_left
from heapq import heapify,heappush,heappop
# from numba import njit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np    # numpy.lcm()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk
# import networkx as nx
# G = Graph()

# slist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

if N == 1:
    print(0)
    exit()

ans = 0
cnt_primes = Counter(prime_factorize(N))

for i in cnt_primes:
    j = 1
    while cnt_primes[i]>=0:
        cnt_primes[i] -= j
        if cnt_primes[i]>=0:
            ans += 1
        else:
            break
        j += 1

print(ans)
a=(input())
b=float(input())
print(a*b)
print(2*(a+b))

### FIXED CODE ###

a,b=list(map(int,input().split()))
print(str(a*b) + " " + str(2*a+2*b))
def solve( p, t ):
	global isExist
	global n
	global A
	isExist[ t ] = True
	if p < n:
		solve( p+1, t-A[p] )
		solve( p+1, t )

isExist = [False]*2001 
n = int( input() )
A = [ int( val ) for val in input().split( " " ) ]
q = int( input() )
M = [ int( val ) for val in input().split( " " ) ]
s = sum( A )
solve( 0, s )
for i in range( 0, q ):
	if isExist[ M[i] ]:
		print( "yes" )
	else:
		print( "no" )

### FIXED CODE ###

def solve( p, t ):
	global isExist, n, A
	isExist[ t ] = True
	if p < n:
		solve( p+1, t-A[p] )
		solve( p+1, t )
	else:
		return

isExist = [False]*2001 
n = int( input() )
A = [ int( val ) for val in input().rstrip().split( ' ' ) ]
q = int( input() )
M = [ int( val ) for val in input().rstrip().split( ' ' ) ]
s = sum( A )
solve( 0, s )
for i in range( 0, q ):
	if isExist[ M[i] ]:
		print( "yes" )
	else:
		print( "no" )
# coding: utf-8
import math


def solve(*args: str) -> str:
    _ = int(args[0])
    D = sorted(list(map(int, args[1].split())))

    max_d = D[-1]

    nodes = [0]*(max_d+1)
    for d in D:
        nodes[d] += 1

    ret = 1
    for i in range(max_d+1):
        if i < 2:
            ret *= 1 if 0 < nodes[i] else 0
        else:
            h = math.factorial(nodes[i-1] + nodes[i]-1)
            h //= math.factorial(nodes[i])
            ret *= h

    return str(ret % 998244353)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    _ = int(args[0])
    D = list(map(int, args[1].split()))

    max_d = max(D)

    nodes = [0]*(max_d+1)
    for d in D:
        nodes[d] += 1

    ret = 0
    if D[0] == 0 and nodes.count(0) == 0 and nodes[0] == 1:
        ret = 1
        for i in range(2, max_d+1):
            ret *= pow(nodes[i-1], nodes[i], 998244353)

    return str(ret % 998244353)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
# -*- coding: utf-8 -*-
"""
Created on Sat May  2 00:21:08 2020

@author: Kanaru Sato
"""

n = int(input())
h = list(map(int, input().split()))
memo = [0]*n

#topdown
def cost(n):
    if n == 0:
        return 0
    elif n == 1:
        return abs(h[1]-h[0])
    elif memo[n]:
        return memo[n]
    else:
        memo[n] = min(cost(n-2)+abs(h[n]-h[n-2]),cost(n-1)+abs(h[n]-h[n-1]))
        return memo[n]

print(cost(n-1))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat May  2 00:21:08 2020

@author: Kanaru Sato
"""
import sys
sys.setrecursionlimit(10 ** 6)

N = int(input())
h = list(map(int, input().split()))
memo = [-1]*N
memo[0] = 0
memo[1] = abs(h[1]-h[0])

#topdown
def cost(n):
    if n <= 1 or memo[n] >= 0:
        return memo[n]
    else:
        memo[n] = min(cost(n-2)+abs(h[n]-h[n-2]),cost(n-1)+abs(h[n]-h[n-1]))
        return memo[n]

print(cost(N-1))
import collections
n = int(input())
arr = list(map(int,input().split()))
cnt = collections.defaultdict(int)
for val in arr:
    cnt[val] += 1
sums = sum(arr)
q = int(input())
for _ in range(q):
    b, c = map(int,input().split())
    diff = (c-b)*(cnt[b])
    sums += diff
    print(sums)
    cnt[c] += nt[b]
    cnt[b] = 0

### FIXED CODE ###

import collections
n = int(input())
arr = list(map(int,input().split()))
cnt = collections.defaultdict(int)
for val in arr:
    cnt[val] += 1
sums = sum(arr)
q = int(input())
for _ in range(q):
    b, c = map(int,input().split())
    diff = (c-b)*(cnt[b])
    sums += diff
    print(sums)
    cnt[c] += cnt[b]
    cnt[b] = 0
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
import time
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
#    n = 500
    cos = [[min(i,j,n-1-i,n-1-j) for i in range(n)] for j in range(n)]
#    p = [(i//n,i%n) for i in range(n**2)]
    p = [((int(i)-1)//n,((int(i)-1)%n) for i in ipt().split()]
    ans = 0
    q = []
    al = [[True]*n for i in range(n)]

    for px,py in p:
        ans += cos[px][py]
        q.append((px,py,cos[px][py]))
        al[px][py] = False
        while q:
            qx,qy,qc = q.pop()
            if qx != 0 and cos[qx-1][qy] > qc:
                cos[qx-1][qy] = qc
                q.append((qx-1,qy,qc+al[qx-1][qy]))
            if qx != n-1 and cos[qx+1][qy] > qc:
                cos[qx+1][qy] = qc
                q.append((qx+1,qy,qc+al[qx+1][qy]))
            if qy != 0 and cos[qx][qy-1] > qc:
                cos[qx][qy-1] = qc
                q.append((qx,qy-1,qc+al[qx][qy-1]))
            if qy != n-1 and cos[qx][qy+1] > qc:
                cos[qx][qy+1] = qc
                q.append((qx,qy+1,qc+al[qx][qy+1]))

    print(ans)

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
import time
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
#    n = 500
    cos = [[min(i,j,n-1-i,n-1-j) for i in range(n)] for j in range(n)]
#    p = [(i//n,i%n) for i in range(n**2)]
    p = [((int(i)-1)//n,(int(i)-1)%n) for i in ipt().split()]
    ans = 0
    q = []
    al = [[True]*n for i in range(n)]

    for px,py in p:
        ans += cos[px][py]
        q.append((px,py,cos[px][py]))
        al[px][py] = False
        while q:
            qx,qy,qc = q.pop()
            if qx != 0 and cos[qx-1][qy] > qc:
                cos[qx-1][qy] = qc
                q.append((qx-1,qy,qc+al[qx-1][qy]))
            if qx != n-1 and cos[qx+1][qy] > qc:
                cos[qx+1][qy] = qc
                q.append((qx+1,qy,qc+al[qx+1][qy]))
            if qy != 0 and cos[qx][qy-1] > qc:
                cos[qx][qy-1] = qc
                q.append((qx,qy-1,qc+al[qx][qy-1]))
            if qy != n-1 and cos[qx][qy+1] > qc:
                cos[qx][qy+1] = qc
                q.append((qx,qy+1,qc+al[qx][qy+1]))

    print(ans)

    return

if __name__ == '__main__':
    main()
N = int(input())
M = str(input())

if len(N)>7:
    print(M[0:7]+'...')

### FIXED CODE ###

N = int(input())
M = str(input())

if len(M)>N:
    print(M[0:N]+'...')
else:
    print(M)
n=input()
for i in range(3):
  if n[i]==1:
    n[i]=9
  else:
    n[i]=1
print(n)

### FIXED CODE ###

n=input()
ans=""
for i in range(3):
  if n[i]=="1":
    ans+="9"
  else:
    ans+="1"
print(ans)
n, k = map(int, input().split())

num = list(map(int, input().split()))
t = [-1] * n
count = 0
s = 1

while t[s - 1] == -1:
  if count == k:
    break

  t[s - 1] = count
  count += 1
  s = num[s - 1]
else:
  z = (k - t[s - 1]) % (count - t[s - 1])
  w = t.index(t[s - 1] + z + 1)
print(w)


### FIXED CODE ###

a = input()
b = input()

if(a[0:len(a)] == b[0:len(a)]):
  print('Yes')
else:
  print('No')
#D
s_list=list(input())
q=int(input())
r=0
sl_list=[]
for i in range(q):
    ope=input().split()
    if ope[0]=='1':
        r+=1
    else:
        if (int(ope[1])+r)%2 == 1:
            sl_list.append(ope[2])
        else:
            s_list.append(ope[2])
s_list=sl_list.reverse() + s_list
if r%2 !=0:
    s_list.reverse()
print(''.join(s_list))

### FIXED CODE ###

#D
s_list=list(input())
q=int(input())
r=0
sl_list=[]
for i in range(q):
    ope=input().split()
    if ope[0]=='1':
        r+=1
    else:
        if (int(ope[1])+r)%2 == 1:
            sl_list.append(ope[2])
        else:
            s_list.append(ope[2])
sl_list.reverse()
s_list=sl_list + s_list
if r%2 !=0:
    s_list.reverse()
print(''.join(s_list))