Harryxun/stf_run huggingface dataset:
from bisect import insort
from collections import deque
from heapq import heapify, heappop, merge, heapreplace, heappush


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[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


def solve(aa, uft):
    roots = {x: [] for x, r in enumerate(uft.table) if r < 0}
    if n < (len(roots) - 1) * 2:
        return 'Impossible'
    for x, a in enumerate(aa):
        roots[uft._root(x)].append(a)
    queue = []
    for l in roots.values():
        l.sort()
        queue.append(deque(l))
    queue.sort()
    queue = deque(queue)
    ans = 0
    while len(queue) > 1:
        # print(queue)
        buf = []
        dq1 = queue.popleft()
        dq2 = queue.popleft()
        if len(dq1) == 1:
            while len(dq2) == 1 and len(queue) > 0:
                buf.append(dq2)
                dq2 = queue.popleft()
        ans += dq1.popleft() + dq2.popleft()
        insort(queue, deque(merge(dq1, dq2)))
        if buf:
            queue.extendleft(reversed(buf))
    return ans


n, m = map(int, input().split())
aa = list(map(int, input().split()))
uft = UnionFind(n)
for _ in range(m):
    uft.union(*map(int, input().split()))
print(solve(aa, uft))


### FIXED CODE ###

from collections import deque, defaultdict
from heapq import heapify, heappop, merge, heapreplace


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self._root(self.table[x])
            return self.table[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


def solve(aa, uft):
    roots = defaultdict(list)
    for x, a in enumerate(aa):
        roots[uft._root(x)].append(a)
    if len(roots) == 1:
        return 0
    if n < (len(roots) - 1) * 2:
        return 'Impossible'
    ans = 0
    queue = []
    for l in roots.values():
        l.sort()
        ans += l[0]
        queue.append(l[1:])
    lm = n - m - 2
    if lm > 0:
        mm = merge(*queue)
        for _ in range(lm):
            ans += next(mm)
    return ans


n, m = map(int, input().split())
aa = list(map(int, input().split()))
uft = UnionFind(n)
for _ in range(m):
    uft.union(*map(int, input().split()))
print(solve(aa, uft))
print chr(ord(input()) + 1)

### FIXED CODE ###

c = input()
print(chr(ord(c) + 1))
n=int(input())
mod=10**9+7

def prime_factorization(n):
    '''
    素因数分解を求める

    Parameters:
    n : int
        求める数
    
    Returns:
    r : list
        素因数分解の結果
    '''
    r=[1]*(n+1)
    for i in range(1,n+1):
        for j in range(2,i+1):
            while i % j == 0:
                r[j] += 1
                i //= j
    
    return r

r = prime_factorization(N)
ans = 1
for i in r:
    ans *= i
    ans %= mod

print(ans)


### FIXED CODE ###

N=int(input())
mod=10**9+7

def prime_factorization(n):
    '''
    素因数分解を求める

    Parameters:
    n : int
        求める数
    
    Returns:
    r : list
        素因数分解の結果
    '''
    r=[1]*(n+1)
    for i in range(1,n+1):
        for j in range(2,i+1):
            while i % j == 0:
                r[j] += 1
                i //= j
    
    return r

r = prime_factorization(N)
ans = 1
for i in r:
    ans *= i
    ans %= mod

print(ans)
import numpy as np

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

            
def judge(x, lst):

    length = len(lst)
    all_pair = (length*(length-1) // 2) + length
    
    lst_r = [-1 if i < x else 1 for i in lst]
    array = np.cumsum(np.array(lst_r))
    lst_accum = array - min(array) + 1
    
    bit = Bit(max(lst_accum))
    ans = 0
    for i, p in enumerate(lst_accum):
        bit.add(p, 1)
        ans += i + 1 - bit.sum(p)
    
    ans = all_pair - ans
    if ans >= (all_pair//2) + 1:
        return True
    else:
        return False

    
lst = sorted(lst)
low = 0
high = len(lst) - 1
t = (low+high) // 2
while low < high:
    i = lst[t]
    if judge(i, lst):
        if low == t:
            break
        low = t
        t = (low+high) // 2
    else:
        high = t
        t = (low+high) // 2
        
print(lst[high]) if judge(lst[high], lst) else print(lst[t])

### FIXED CODE ###

from itertools import accumulate
from math import ceil
 
N = int(input())
A = list(map(int, input().split()))
 
if N == 1:
    print(A[0])
    exit()
 
 
class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)
 
    def reset(self):
        self.bit = [0] * (self.size + 1)
 
 
BIT = BinaryIndexedTree(N)  # Binaryの先頭の分
lo, hi = -1, 10 ** 9 + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2
 
    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]
 
    # 累積和をとる
    Binary = list(accumulate(Binary))
 
    # BITを初期化
    BIT.reset()
 
    # 転倒数っぽいものを数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += BIT.sum(Binary_sorted[b]) + (b >= 0)
        BIT.add(Binary_sorted[b], 1)
 
    if inversion >= ceil((N * (N + 1) / 2) / 2):
        lo = X
    else:
        hi = X
 
print(lo)
# coding: utf-8
# Your code here!
N, K = map(int,input().split())

link = [[] for i in range(N)]
link[0] = [i for i in range(1,N)]
for i in range(1,N):
    link[i].append(0)

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

if N == 2 and K == 0:
    print(1)
    print("1 2")
elif N == 2 and K == 1:
    print(-1)
elif comb(N-1,2) < K:
    print(-1)
else:
    maxnum = comb(N-1,2)
    for i in range(1,N):
        for j in range(1,N):
            if i < j:
                if maxnum != K:
                    link[i].append(j)
                    link[j].append(i)
                    maxnum -= 1
                else:
                    continue
    print(sum([len(l) for l in link])//2)
    for i in range(N):
        for j in link[i]:
            if i < j:
                print(i+1, j+1)

                
        
    


### FIXED CODE ###

# coding: utf-8
# Your code here!
N, K = map(int,input().split())

link = [[] for i in range(N)]
link[0] = [i for i in range(1,N)]
for i in range(1,N):
    link[i].append(0)

def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

if N == 2 and K == 0:
    print(1)
    print("1 2")
elif N == 2 and K == 1:
    print(-1)
elif comb(N-1,2) < K:
    print(-1)
else:
    maxnum = comb(N-1,2)
    for i in range(1,N):
        for j in range(1,N):
            if i < j:
                if maxnum != K:
                    link[i].append(j)
                    link[j].append(i)
                    maxnum -= 1
                else:
                    continue
    print(sum([len(l) for l in link])//2)
    for i in range(N):
        for j in link[i]:
            if i < j:
                print(i+1, j+1)
n=int(input())
a=[int(z) for z in input().split()]
x=1
for i in a:
    x*=i
    if x>10**18:
        print("-1")
        break
if x<=10**18:
    print(x)

### FIXED CODE ###

a,b=map(int,input().split())
print(a*b)
N, K = map(int, input().rstrip().split(' '))
h = list(map(int, input().rstrip().split(' ')))
def frog_jump(n, height=h):
  if len(height[:n]) == 1:
    return 0
  now_height = height[n-1]
  start = n-1-K if n-1-K >= 0 else 0
  min_lst = [frog_jump(i) + abs(now_height-j) for i, j in enumerate(height[start:n-1], start+1)]
  # print(min_lst)
  min_cost = min(min_lst)
  return min_cost

print(frog_jump(N))

### FIXED CODE ###

N, K = map(int, input().rstrip().split(' '))
frog_lst = list(map(int, input().rstrip().split(' ')))
frog_jump_lst = []

def frog_jump(frog_jump_lst=[], index=0):
  if not frog_jump_lst:
    frog_jump_lst.append(0)
  else:
    now_pos = frog_lst[index]
    k = min(K, len(frog_jump_lst))
    pattern = [abs(now_pos - frog_lst[index-i]) + frog_jump_lst[-i] for i in range(1,k+1)]
    frog_jump_lst.append(min(pattern))

for j in range(N):
  frog_jump(frog_jump_lst, j)
print(frog_jump_lst[-1])
l=[input() for _ in range(5)]
l_1=[]
for i in l:
  if i%10!=0:
    l_1.append(((i+9)//10)*10)
  else:l_1.append(i)
nnn=9999999    
for i in range(5):
  num_1=0
  for j in range(5):
    if i==j:
      num_1+=l[j]
    else:num_1+=l_1[j]
  nnn=min(nnn,num_1)
print(nnn)

### FIXED CODE ###

l=[int(input()) for _ in range(5)]
l_1=[]
for i in l:
  if i%10!=0:
    l_1.append(((i+9)//10)*10)
  else:l_1.append(i)
nnn=9999999    
for i in range(5):
  num_1=0
  for j in range(5):
    if i==j:
      num_1+=l[j]
    else:num_1+=l_1[j]
  nnn=min(nnn,num_1)
print(nnn)
num=1
maxw=input()
while maxw<>0:
    N=input()
    ws,ps=[],[]
    for i in range(N):
        tmp=input()
        ws.append(tmp[1])
        ps.append(tmp[0])
    dp=[[0]*(maxw+1) for i in range(len(ws)+1)]
    ret=0
    for i in range(len(ws)):
        for j in range(maxw+1):
            if (j+ws[i])<=maxw:
                dp[i+1][j+ws[i]]=max(dp[i+1][j+ws[i]],dp[i][j]+ps[i])
                ret=max(dp[i+1][j+ws[i]],ret)
    print "Case %d:"%num
    print ret
    print dp[len(ws)].index(ret)
    num+=1
    maxw=input()

### FIXED CODE ###

num=1
while True:
    maxw=input()
    if maxw==0:break
    print "Case %d:"%num
    dp,w,v=[0]*1001,[0]*1001,[0]*1001
    n=input()
    for i in xrange(n):
        v[i],w[i]=map(int,raw_input().strip().split(","))
    for i in xrange(n):
        for j in xrange(maxw,-1,-1):
            if j+w[i]<=maxw:
                dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i])
    print max(dp)
    print dp.index(max(dp))
    num+=1
a,b,c = input().split()
 
import math
 
a = int(a)
b = int(b)
c = int(c)
 
if math.isclose(math.sqrt(c) - math.sqrt(b) - math.sqrt(a), 0, abs_tol=1e-10):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

if 4 * a * b < (c - a- b)**2 and c - a- b > 0:
    print("Yes")
else:
    print("No")
import bisect
N = int(input())
S = list(input())
R_i = []
G_i = []
B_i = []
for i in range(N):
  if S[i] == "R": R_i.append(i)
  elif S[i] == "G": G_i.append(i)
  else: B_i.append(i)

r = len(R_i)
g = len(G_i)
b = len(B_i)

ans = 0
for i in range(N):
  for j in range(1, N-i):
    if S[i] == "R":
      print(i+j in G_i , b - bisect.bisect_right(B_i,i + j) > 0)
      if i+j in G_i and b - bisect.bisect_right(B_i,i + 2 * j) > 0:
        ans += b - bisect.bisect_right(B_i,i + 2 * j)
        if i + j + j in b: ans -= 1
      elif i+ j in B_i and g - bisect.bisect_right(G_i,i + 2 * j) > 0:
        ans += g - bisect.bisect_right(G_i,i + 2 * j)
        if i + j + j in g: ans -= 1
    elif S[i] == "G":
      if i+j in R_i and b - bisect.bisect_right(B_i,i + 2 * j) > 0:
        ans += b - bisect.bisect_right(B_i,i + 2 * j)
        if i + j + j in b: ans -= 1
      elif i+j in B_i and r - bisect.bisect_right(R_i,i + 2 * j) > 0:
        ans += r - bisect.bisect_right(R_i,i + 2 * j)
        if i + j + j in r: ans -= 1
    else:
      if i+j in R_i and g - bisect.bisect_right(G_i,i + 2 * j) > 0:
        ans += g - bisect.bisect_right(G_i,i + 2 * j)
        if i + j + j in g: ans -= 1
      elif i+j in G_i and r - bisect.bisect_right(R_i,i + 2 * j) > 0:
        ans += r - bisect.bisect_right(R_i,i + 2 * j)
        if i + j + j in r: ans -= 1
print(ans)

### FIXED CODE ###

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

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

def f(S):
  N = len(S)
  ret = 0
  for i in range(N):
    for j in range(i+1, N):
      k = j + j -i
      if k >= N:
        break
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        ret += 1
  return ret

ans = R * B * G - f(S)
print(ans)
N = int(input())
vector_list = ([int(x) for x in input().split()])
cost_list = ([int(x) for x in input().split()])
ans = 0
for i in range(len(vector_list)):
  if vector_list[i]-cost_list[i]>0:
    ans += vector_list[i]-cost_list[i]

print(ans)

 

### FIXED CODE ###

#スペース区切りの整数の入力
A, B, T= map(int, input().split())
ans = (int(T/A))*B
print("{}".format(ans))
n = int(input())

if n >= 1800: print(1)
elif n >= 1600: print(2)
elif n >= 1400: print(3)
elif n >= 1200: print(4)
elif n >= 1000: print(5)
elif n >= 800: print(6)
elif n >= 600: print(7)
elif n >= 400:: print(8)

### FIXED CODE ###

n = int(input())
 
if n >= 1800: print(1)
elif n >= 1600: print(2)
elif n >= 1400: print(3)
elif n >= 1200: print(4)
elif n >= 1000: print(5)
elif n >= 800: print(6)
elif n >= 600: print(7)
elif n >= 400: print(8)
def pr(a):
    for i in range(len(a)):
        print(a[i],end="")
        if i == len(a)-1:
            print("")
        else :
            print(" ",end="")

n = int(input())
a = []
for i in range(n):
    x = input().split()
    if x[0] == "insert":
        a.insert(0,int(x[1]))
    elif x[0] == "delete":
        a.remove(int(x[1]))
    elif x[0] == "deleteFirst":
        a.pop(0)
    elif x[0] == "deleteLast":
        a.pop()

pr(a)



### FIXED CODE ###

from collections import deque

def pr(a):
    for i in range(len(a)):
        if i == len(a)-1:
            print(a[i])
        else:
            print(a[i],end = " ")

n = int(input())
q = deque()
for i in range(n):
    x = input()
    l = len(x)
    if x[0] == "i":
        q.insert(0,x[7:])
    elif x[6] == " ":
        try:
            q.remove(x[7:])
        except:
            pass
    elif l > 10:
        q.popleft()
    elif l > 6:
        q.pop()

print(*q)
def beautiful:
     a,b,c = input().split()
      if abs(b-a) == abs(c-b):
            print('YES')
      else:
            print('NO')

beautiful()

### FIXED CODE ###

a,b,c=input().split()

a=int(a)
b=int(b)
c=int(c)

if b-a==c-b:
    print("YES")
else:
    print("NO")
input()
a=list(int,input())
print(a[::-1])

### FIXED CODE ###

input()
print(' '.join(input().split()[::-1]))
from scipy import special
N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {}
    for a, b in links:
        if a in d:
            d[a].add(b)
        else:
            d[a] = {b}
        if b in d:
            d[b].add(a)
        else:
            d[b] = {a}
    root = {1}
    ans = K
    while True:
        a = K - 2
        if 1 in root:
            a = K - 1
        children = set()
        for i in root:
            for j in d[i]:
                d[j].remove(i)
            b = len(d[i])
            if a < b:
                print(0)
                break
            if b == 0:
                continue
            ans *= special.perm(a, b, exact=True)
            children |= d[i]
        else:
            if len(children) == 0:
                print(ans % mod)
                break
            root = children
            continue
        break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
x = input()

if x = 0 :
  print(1)
else :
  print(0)

### FIXED CODE ###

x = int(input())

if x == 0 :
    print(1)
else :
    print(0)
S = input()

if S == "SUN":
    cmd = 0
elif S == "MON":
    cmd = 1
elif S == "TUE":
    cmd = 2
elif S == "WED":
    cmd = 3
elif S == "THU":
    cmd = 4
elif S == "FRY":
    cmd = 5
elif S == "SAT":
    cmd = 6

if cmd == 0:
    print(7)
else:
    print(cmd)

### FIXED CODE ###

S = str(input())

if S == "SUN":
    cmd = 0
elif S == "MON":
    cmd = 1
elif S == "TUE":
    cmd = 2
elif S == "WED":
    cmd = 3
elif S == "THU":
    cmd = 4
elif S == "FRI":
    cmd = 5
elif S == "SAT":
    cmd = 6

print(7-cmd)
def main():
    global n, peso, dp

    n = int(input())
    peso = [int(x) for x in input().split()]
    dp = [-1]*n
    
    peso.append(10**9)
    
    print(frog(0))
    
def frog(i):
    global n, peso, dp
    
    if i >= n - 1:
        return 0

    if dp[i] != -1:
        return dp[i]

    dp[i] = min(abs(peso[i + 1] - peso[i]) + frog(i + 1),
            abs(peso[i + 2] - peso[i]) + frog(i + 2))
    
    return dp[i]

main()

### FIXED CODE ###

n = int(input())
h = [int(x) for x in input().split()]

def abs(x):
    if x >= 0:
        return x
    return -x

c = [0]
c.append(abs(h[1] - h[0]))
for k in range(2, n):
    cnext = min(c[k-2] + abs(h[k]-h[k-2]), c[k-1] + abs(h[k] - h[k-1]))
    c.append(cnext)

print(c[-1])
in = int(input())
for i in list(range(1,10)):
     if in / i >= 10:
             print("No")
     else:
             print("Yes")

### FIXED CODE ###

k = int(input())
for i in range(1,10):
    if k // i <= 9 and k % i == 0:
       print("Yes")
       exit()
     
print("No")
n = int(input())
c0 = 0
c1 = 0
c2 = 0
c3 = 0
for i in ragne(n):
  s = input()
  if s == 'AC':
    c0 += 1
  elif s == 'WA':
    c1 += 1
  elif s == 'TLE':
    c2 += 1
  else:
    c3 += 1
print(f'AC x {c0}')
print(f'WA x {c1}')
print(f'TLE x {c2}')
print(f'RE x {c3}')

### FIXED CODE ###

n = int(input())
c0 = 0
c1 = 0
c2 = 0
c3 = 0
for i in range(n):
  s = input()
  if s == 'AC':
    c0 += 1
  elif s == 'WA':
    c1 += 1
  elif s == 'TLE':
    c2 += 1
  else:
    c3 += 1
print(f'AC x {c0}')
print(f'WA x {c1}')
print(f'TLE x {c2}')
print(f'RE x {c3}')
N, M, C = map(int, input().split)
Blis = [int(x) for x in input().split()]
k = 0
for i in range(N):
  Alis = [int(x) for x in input().split()]
  total = 0
  for j in range(M):
    total = total + Alis[j]*Blis[j]
  total = total + C
  if total > 0:
    k = k + 1
print(k)    

### FIXED CODE ###

N, M, C = map(int, input().split())
Blis = [int(x) for x in input().split()]
k = 0
for i in range(N):
  Alis = [int(x) for x in input().split()]
  total = 0
  for j in range(M):
    total = total + (Alis[j])*(Blis[j])
  total = total + C
  if total > 0:
    k = k + 1
print(k)
a,b=input().split()
if not (int)(a)%2==0 and not (int)(b)%2==0:
  print("Odd")
  return
print("Even")

### FIXED CODE ###

a_, b_ = input().split()
a = (int)(a_)
b = (int)(b_)

if a%2==0:
    print("Even")
elif b%2==0:
    print("Even")
else:
    print("Odd")
from collections import deque
def hate(x,y):
    cur_hate = 0
    cur_q = set()
    next_q = set()
    cur_q.add((x,y))
    already = set()
    flag = False
    while True:
        while cur_q:
            x,y = cur_q.pop()
            for i in range(4):
                next_x = x+dx[i]
                next_y = y+dy[i]
                if not (next_x,next_y) in already:
                    if grid[next_y][next_x] == "o":
                        if cur_hate != 0:
                            return cur_hate
                        flag = True
                    if grid[next_y][next_x] == "#":
                        next_q.add((next_x,next_y))
                    else:
                        cur_q.add((next_x,next_y))
                    if grid[y][x] != "o":
                        already.add((x,y))
        if flag:
            for x,y in already:
                grid[y][x] ="o"
            return 0
        cur_hate += 1
        cur_q = next_q
        next_q = set()
n = int(input())
grid = []
grid.append(["o"]*(n+2))
for i in range(n):
    grid.append(["o"]+["#"]*n+["o"])
grid.append(["o"]*(n+2))
dx = [0,1,0,-1]
dy = [1,0,-1,0]
ans = 0
p = list(map(int,input().split()))
for i in range(n**2):
    pos = p[i]
    x = (pos-1)%n+1
    y = (pos-1)//n+1
    h = hate(x,y)
    ans += h
    if h == 0:
        grid[y][x] = "o"
    else:
        grid[y][x] = "."
print(ans)


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4,i4[:])',cache=True)
def main(n,p):
    ans = 0
    w = n+2
    grid = np.ones((w,w),np.int32)
    dis = np.zeros((w,w),np.int32)
    for i in range(1,n+1):
        for j in range(1,n+1):
            dis[i][j] = min(i,n-i+1,j,n-j+1)-1
    grid = grid.ravel()
    dis = dis.ravel()
    stack = np.empty_like(grid)
    for pos in p:
        pos -= 1
        x = pos % n + 1
        y = pos // n + 1
        v = y*w+x
        ans += dis[v]
        grid[v] = 0
        k = min(dis[v-1],dis[v+1],dis[v+w],dis[v-w])
        cur = 0
        stack[0] = v
        while cur >= 0:
            v = stack[cur]
            cur -= 1
            for dx in (-1,1,w,-w):
                next_v = v + dx
                k = dis[v]+grid[v]
                if dis[next_v] > k:
                    dis[next_v] = k
                    cur += 1
                    stack[cur] = next_v
    return ans

n = int(readline())
p = np.array(readline().split(),np.int32)
print(main(n,p))
#Lucky 7
input(nm)
num=int(nm)
num3=num/100
num2=num/10%10
num1=num%10
if(num3==7 or num2==7 or num1==7):
    print("Yes")
else:
    print("No")
    



### FIXED CODE ###

#Lucky 7
num=int(input(""))
num3=num//100
num2=num//10%10
num1=num%10
if(num3==7 or num2==7 or num1==7):
    print("Yes")
else:
    print("No")
a = list(map(int,input().split()))
x1 = sum([a[h] if h%2==0 else -a[h] for h in range(n)])
print(x1,end = ' ')

for i in range(n-1):
	if i == 0:
		b = a[i]*2 - x1
		print(b,end=' ')
	else:
		print(a[i]*2 - b,end=' ')
		b = a[i]*2 - b

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
x1 = sum([a[h] if h%2==0 else -a[h] for h in range(n)])
print(x1,end = ' ')

for i in range(n-1):
	if i == 0:
		b = a[i]*2 - x1
		print(b,end=' ')
	else:
		print(a[i]*2 - b,end=' ')
		b = a[i]*2 - b