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

cin = open(0).read().strip().split('\n')
n = int(cin[0])
p = list(map(int, cin[1].split(' ')))

space = [1]*(n*n)

dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]

dist = [0]*(n*n)
for r in range(n):
    for c in range(n):
        dist[r*n+c] = min(r, (n-1)-r, c, (n-1)-c)

ans = 0
for pi in p:
    row, col = divmod(pi-1, n)
    q = [(row, col)]
    ans += dist[pi-1]
    space[row*n + col] = 0

    while q:
        ph, pw = q.pop()
        for dyi, dxi in zip(dy,dx):
            if 0<=ph+dyi<n and 0<=pw+dxi<n:
                if dist[(ph+dyi)*n+(pw+dxi)] > dist[ph*n+pw]+space[(ph)*n+(pw)]:
                    q.append((ph+dyi,pw+dxi))
                    dist[(ph+dyi)*n+(pw+dxi)] = dist[ph*n+pw]+space[(ph)*n+(pw)]

print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!

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

n,*p = map(int,read().split())
N = n*n

dist = [0]*N

for a in range(n):
    for b in range(n):
        dist[a*n+b] = min(a,n-1-a,b,n-1-b)

#print(dist)


#ans = [0]*N
ans = 0
iru = [1]*N

for pi in p:
    pi -= 1

    ans += dist[pi]
    iru[pi] = 0

    q = [pi]
    #更新
    
    while q:
        #print(q)
        v = q.pop()
        for i in [-n,-1,1,n]:
            if i==1 and v%n==n-1: continue
            if i==-1 and v%n==0: continue
            nv = v+i
            if 0 <= nv < N and dist[nv] > dist[v] + iru[v]:
                q.append(nv)
                dist[nv] = dist[v] + iru[v]
        
                    
    #print(dist)        

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

from statistics import mean

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

def separate_equally(nums):
    left = 0
    right = sum(nums)
    pre_diff = abs(left - right)
    for num in nums:
        left += num
        right -= num
        diff = abs(left - right)
        if diff < pre_diff:
           pre_diff = diff
        else:
            return [left - num, right + num]

min_score = float('inf')
for i in range(2, N - 1):
    left_A = A[:i]
    right_A = A[i:]
    sums = separate_equally(left_A)
    sums.extend(separate_equally(right_A))
    score = max(sums) - min(sums)
    if score < min_score:
        min_score = score
    
print(min_score)

### FIXED CODE ###

from statistics import mean

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

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

left_middle = 0
right_middle = 2

ans = float('inf')

for middle in range(1, N - 2):
    left_sum = S[left_middle]
    right_sum = S[middle] - left_sum
    diff = abs(left_sum - right_sum)

    for i in range(left_middle+1, middle):
        left_sum = S[i]
        right_sum = S[middle] - left_sum
        if diff > abs(left_sum - right_sum):
            left_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    left_sum = S[right_middle] - S[middle]
    right_sum = S[-1] - S[right_middle]
    diff = abs(left_sum - right_sum)

    for i in range(right_middle + 1, N):
        left_sum = S[i] - S[middle]
        right_sum = S[-1] - S[i]
        if diff > abs(left_sum - right_sum):
            right_middle = i
            diff = abs(left_sum - right_sum)
        else:
            break
    
    s1 = S[left_middle]
    s2 = S[middle] - s1
    s3 = S[right_middle] - s1 - s2
    s4 = S[-1] - s1 - s2 - s3

    score = max(s1, s2, s3, s4) - min(s1, s2, s3, s4)
    ans = min(ans, score)

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

k, s = map(int, input().split())
ans = 0
for a in range(k+1):
    for b in range(k+1):
        for c in range(k+1):
            if a + b + c == s:
                ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int, input().split())
cnt = 0
for i in range(k+1):
    for j in range(k+1):
        z = s - i - j
        if z >= 0 and z <= k:
            cnt+=1
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        for j in range(max_capacity, w - 1, -1):
            if dp[j] < dp[j - w] + v:
                dp[j] = dp[j - w] + v
    return dp[max_capacity]


def solve_better(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

# DP
def main():
    N, W = map(int, input().split())

    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))


main()
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[input() for __ in range(M)]

for bc in BC:
    b,c=map(int,bc.split())
    A.extend(list([c]*b))
    A.sort(reverse=True)

print(sum(A[:N]))


### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=[list(map(int,input().split())) for __ in range(M)]
BC.sort(key=lambda x: x[1],reverse=True)

l=[]
for b,c in BC:
    if len(l)+b>N:
        l.extend(list([c]*b))
        break
    else:
        l.extend(list([c]*b))
A.extend(l)
A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    ary = []
    i = 0
    while i < N:
        a, b = map(int, input().split())
        ary += [a] * b
        i += 1

    ans = sorted(ary)[K-1]
    print(ans)

main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    ab = []
    i = 0
    while i < N:
        a, b = map(int, input().split())
        ab.append([a, b])
        i += 1

    ary = sorted(ab)
    j = 0
    for i in ary:
        j += i[1]
        if j >= K:
            print(i[0])
            break

main()
### BUGGY CODE ###

def rec(i, j):
    if (i, j) in dp:
        return dp[i, j]
    if i == 40:
        res = 0
    elif j < w[i] or w[i] < 0:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])
    dp[i, j] = res
    return res

N, K = map(int, input().split())
A = list(map(int, input().split()))
bit = [0] * 40
for i in A:
    for j in range(40):
        bit[j] += (i >> j) & 1
w = [0] * 40
v = [0] * 40
for i in range(40):
    w[i] = 1 << i
    v[i] = (N - bit[i] - bit[i]) * w[i]
dp = {}
x = rec(0, K)
print(x + sum(A))

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
bit = [0] * 41
for i in A:
    for j in range(41):
        bit[j] += (i >> j) & 1
x = {}
for i in range(41):
    x[i, 0] = 2 ** i * bit[i]
    x[i, 1] = 2 ** i * (N - bit[i])
ans = sum(A)
for i in range(41):
    if ((K + 1) >> i) & 1 == 0:
        continue
    f = 0
    for j in range(i):
        f += max(x[j, 0], x[j, 1])
    f += x[i, 0]
    for j in range(i + 1, 41):
        f += x[j, ((K + 1) >> j) & 1]
    ans = max(ans, f)
print(ans)
### BUGGY CODE ###

n = int(input())
ans = n-1

for i in range(1, int(n*0.5)+1):
  if n%i == 0:
    num1 = i
    num2 = n/i
    ans = min(ans, num1+num2-2)
    
print(int(ans))

### FIXED CODE ###

n = int(input())
ans = n-1

for i in range(1, int(n**0.5)+1):
  if n%i == 0:
    num1 = i
    num2 = n/i
    ans = min(ans, num1+num2-2)
    
print(int(ans))
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = min([ S[:i].count('W') + S[i+1:].count('E')  for i in range(N) ])
print(ans)

### FIXED CODE ###

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

ans = S.count('E')
w = 0
e = S.count('E')
for i in range(N):
    if S[i-1] == 'W' and i != 0:
        w += 1
    if S[i] == 'E':
        e -= 1
    if w + e < ans:
        ans = w + e
print(ans)
### BUGGY CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)
    items = [(next(data), next(data)) for _ in range(N)]
    Q = next(data)

    H = min(N + 1, 1 << 9)
    Hb = (H - 1).bit_length()
    dp = [[0] * (MX + 1) for _ in range(H)]
    for i in range(1, H):
        v, w = items[i - 1]
        dpi = dp[i]
        dpip = dp[i >> 1]
        for j in range(w):
            dpi[j] = dpip[j]
        for j in range(w, MX + 1):
            dpi[j] = max(dpip[j], dpip[j - w] + v)

    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue
        ans = []
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    iv, iw = items[node - 1]
                    value += iv
                    weight += iw
                    if weight > L:
                        break
                node >>= 1
                i >>= 1
            else:
                ans.append(value + dp[node][L - weight])
        print(max(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)

    H = min(N + 1, 1 << 10)
    dp = [None] * H
    dp[0] = [0] * (MX + 1)
    IV, IW = [], []
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i >> 1][:]
            dp[i] = dpi
            for j in range(MX, w - 1, -1):
                dpi[j] = max(dpi[j], dpi[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

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

from collections import Counter
s = input()
n = len(s)
# 累積和の準備
sum_list = [0]*(n+1)  # s[0]は０であってほしいから配列数ひとつおおい
_10 = 1
for i in range(1, n + 1):
    sum_list[i] += (sum_list[i-1] + int(s[n-i])*_10) % 2019  # ここでmodしておく
    _10 *= 10
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
c = Counter(sum_list)
ans = 0

for key in c.keys():
    ans += c[key]*(c[key]-1)//2
print(ans)


### FIXED CODE ###

from collections import Counter
s = input()
n = len(s)
# 累積和の準備
sum_list = [0]*(n+1)  # s[0]は０であってほしいから配列数ひとつおおい
_10 = 1
for i in range(1, n + 1):
    sum_list[i] += (sum_list[i-1] + int(s[n-i])*_10 % 2019) % 2019  # ここでmodしておく
    _10 = _10*10 %2019
"""
(s[j]-s[i]/10**i)が区間の整数
区間の整数が2019で割り切れればよい
つまり、(s[j]-s[i]/10**i)≡0 (mod=2019)
ここで10**iと2019(素数)は互いに素なので、
10**iをかけて上の式はs[j]-s[i]≡0 (mod=2019)と同値
s[j]≡s[i] (mod=2019)となる。
"""
c = Counter(sum_list)
ans = 0

for key in c.keys():
    ans += c[key]*(c[key]-1)//2
print(ans)
### BUGGY CODE ###

[n,k]=list(map(int,input().split()))
ablist=[]
suretu=[]
for i in range(n):
    ab=list(map(int,input().split()))
    suretu+=[ab[0]]*ab[1]
    ablist.append(ab)
suretu.sort()
print(suretu[k-1])

### FIXED CODE ###

[n,k]=list(map(int,input().split()))
ablist=[]
for i in range(n):
    ablist.append(list(map(int,input().split())))
ablist=sorted(ablist,key=lambda x:x[0])
bwa=[0]
for i in range(n):
    bwa.append(bwa[-1]+ablist[i][1])
ind=1
while True:
    if bwa[ind-1]<k<=bwa[ind]:
        break
    ind+=1
print(ablist[ind-1][0])
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    a, b, m = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    B = list(map(int, args[2].split()))

    XYC = {}
    for x, y, c in map(str.split, args[3:]):
        key = (int(x)-1, int(y)-1)
        XYC[key] = max(XYC.get(key, 0), int(c))

    ret = 10**12
    for x in range(a):
        for y in range(b):
            ret = min(ret, A[x]+B[y]-XYC.get((x, y), 0))

    return str(ret)


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


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    a, b, m = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    B = list(map(int, args[2].split()))

    XYC = {}
    for x, y, c in map(str.split, args[3:]):
        key = (int(x)-1, int(y)-1)
        XYC[key] = max(XYC.get(key, 0), int(c))

    ret = min(A)+min(B)
    for (x, y), c in XYC.items():
        ret = min(ret, A[x]+B[y]-c)

    return str(ret)


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

n = int(input())
a = list(map(int, input().split()))
checker = [1 for _i in range(10**6+1)]
a.sort()
a.append(-1)
result = 0
for i in range(n):
    if a[i] == a[i+1]:
        checker[a[i]] = 0
    result += checker[a[i]]
    checker[a[i]] = 0
    x = 2
    while a[i]*x <= 10**6:
        checker[a[i]*x] = 0
        x += 1
print(result)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
checker = [1 for _i in range(10**6+1)]
a.sort()
a.append(-1)
result = 0
for i in range(n):
    if a[i] == a[i-1]:
        continue
    if a[i] == a[i+1]:
        checker[a[i]] = 0
    result += checker[a[i]]
    checker[a[i]] = 0
    x = 2
    while a[i]*x <= 10**6:
        checker[a[i]*x] = 0
        x += 1
print(result)
### BUGGY CODE ###

S = input()
N=len(S)
ans=[0]*N
index=[]#このインデックスの上に来たら探索終了
mmm=10**100

#あらかじめDPでどのマスにいたらどこに行くかを

for i in range(N-1):
  if (S[i]=="R" and S[i+1]=="L"):
    index.append(i)


    
for i in range(N):
  position=i
  count=0
  while(count<mmm):
    if position in index:
      ans[position+(mmm-count)%2]+=1
      break
    else:
      count+=1
      if S[position]=="R":
        position+=1
      elif S[position]=="L":
        position-=1
print(' '.join(map(str, ans)))

### FIXED CODE ###

S=input()
"""
#最終的にどこかに収束するはず
#Rから出発した人はLがある場所まで進み、あとはLとRで反復
Lも同様

"""
ans=[0]*len(S)
R,L=0,0
points=[]#i,i+1、R,Lの4要素リストが格納
for i in range(len(S)-1):
    if S[i]=="R" and S[i+1]=="R":#RかLが連続している
        R+=1
    elif S[i]=="L" and S[i+1]=="L":#RかLが連続している
        L+=1
    #みんなが集まるポイント
    elif S[i]=="R" and S[i+1]=="L":
        if ans[i]==0:
            ans[i]=1
        if ans[i+1]==0:
            ans[i+1]=1
        #今まで数えてきたRを足す
        ans[i]+=R//2
        ans[i+1]+=R//2+R%2#余りはもらう
        points=[i,i+1]
        R=0#R区間初期化
    #ここまで数えてきたLを前の数値に足す
    elif S[i]=="L" and S[i+1]=="R":
        if len(points)>0 and L>0:
            ans[points[0]]+=L//2+L%2#余りはもらう
            ans[points[1]]+=L//2
        L=0#L区間初期化
        points=[]
#拾い残し回収
if L>0 and len(points)>0:
    ans[points[0]]+=L//2+L%2#余りはもらう
    ans[points[1]]+=L//2

map = map(str, ans)
print(' '.join(map))
### BUGGY CODE ###

from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) # タプルやリストで持っておくと便利

H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
mp = [input() for _ in range(H)]
INF = 10**10
dist = [[INF]*W for _ in range(H)]
dist[x1-1][y1-1] = 0
q = deque()
q.append((x1-1,y1-1)) # スタート地点をenqueue
while(q):
    x, y = q.popleft()
    if x==x2-1 and y==y2-1:
        print (dist[x2-1][y2-1])
        exit()
    else:
        for dx, dy in  dxdy:
            for i in range(1,K+1):
                nx = x + dx*i
                ny = y + dy*i
                if not (0<=nx<H and 0<=ny<W) or mp[nx][ny]=='@':
                    break
                if dist[nx][ny] == INF:
                    q.append((nx,ny))
                dist[nx][ny] = min(dist[nx][ny], dist[x][y] + 1)
print(-1)

### FIXED CODE ###

from collections import deque
dxdy = ((-1,0), (1,0), (0,-1), (0,1)) # タプルやリストで持っておくと便利

H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
mp = [input() for _ in range(H)]
INF = 10**10
dist = [[INF]*W for _ in range(H)]
dist[x1-1][y1-1] = 0
q = deque()
q.append((x1-1,y1-1)) # スタート地点をenqueue
while(q):
    x, y = q.popleft()
    if x==x2-1 and y==y2-1:
        print (dist[x2-1][y2-1])
        exit()
    else:
        for dx, dy in  dxdy:
            for i in range(1,K+1):
                nx = x + dx*i
                ny = y + dy*i
                if not (0<=nx<H and 0<=ny<W) or mp[nx][ny]=='@':
                    break
                #print(nx,ny,x,y)
                #print (dist[nx][ny] , dist[x][y])
                if dist[nx][ny] <= dist[x][y]:
                    break 
                #print(nx,ny,x,y)
                if dist[nx][ny] == INF:
                    q.append((nx,ny))
                dist[nx][ny] = dist[x][y] + 1
print(-1)
### BUGGY CODE ###

import collections

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]

ans = sum(A)

for i in range(Q):
    A = [BC[i][1] if x==BC[i][0] else x for x in A]
    print(sum(A))

### FIXED CODE ###

import collections

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]

ans = sum(A)
d = collections.defaultdict(int)

for key in A:
    d[key] += 1

for i in range(Q):
    b,c = BC[i][0],BC[i][1]
    ans += d[b]*(c-b)
    d[c] += d[b]
    d[b] = 0
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
import numpy as np
# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())

def solve():
    b_list = []
    c_list = []
    n, m = map(int, input().split())
    a_list = list(map(int, input().split()))
    for j in range(m):
        b, c = map(int, input().split())
        a_list += [c] * b
        # b_list.append(b)
        # c_list.append(c)

    # for j in range(m):
    #     a_list += [c_list[j]] * b_list[j]

    a_list.sort(reverse=True)
    print(sum(a_list[:n]))

solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
import numpy as np
from collections import defaultdict
d = defaultdict(int)
# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())

def solve():
    # b_list = []
    # c_list = []
    n, m = map(int, input().split())
    d = defaultdict(int)
    a_list = list(map(int, input().split()))

    for a in a_list:
        d[a] += 1

    for j in range(m):
        b, c = map(int, input().split())
        d[c] += b
        # a_list += [c] * b
        # b_list.append(b)
        # c_list.append(c)

    #print(d)
    current_n = 0
    sum = 0
    for k in sorted(d.keys(), reverse=True):
        sum += min(d[k], n - current_n) * k
        current_n += d[k]
        if current_n >= n:
            break
    print(sum)
    # for j in range(m):
    #     a_list += [c_list[j]] * b_list[j]

    # a_list.sort(reverse=True)
    # print(sum(a_list[:n]))


    # a = np.array(a_list, dtype=np.int64)


    #
    # for j in range(m):
    #     a.sort()
    #     to_index = min(b_list[j], sum(a < c_list[j]))
    #     a[:to_index] = c_list[j]
    #
    # print(np.sum(a))
solve()
### BUGGY CODE ###

import sys,heapq

input=sys.stdin.readline

N=int(input())
node=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        node.append((i,j))

_to={key:set([]) for key in node}
_from={key:set([]) for key in node}


for i in range(0,N):
    A=list(map(int,input().split()))
    for j in range(0,N-2):
        if A[j]-1>i:
            if A[j+1]-1>i:
                _to[(i,A[j]-1)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((i,A[j]-1))
            else:
                _to[(i,A[j]-1)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((i,A[j]-1))
        else:
            if A[j+1]-1>i:
                _to[(A[j]-1,i)].add((i,A[j+1]-1))
                _from[(i,A[j+1]-1)].add((A[j]-1,i))
            else:
                _to[(A[j]-1,i)].add((A[j+1]-1,i))
                _from[(A[j+1]-1,i)].add((A[j]-1,i))

day=0
conduct=set([])
q=[]
for key in node:
    if not _from[key]:
        conduct.add(key)
        q.append(key)
sub=[]
heapq.heapify(q)
heapq.heapify(sub)
while q:
    while q:
        x=heapq.heappop(q)
        for n in _to[x]:
            if conduct>=_from[n]:
                conduct.add(n)
                heapq.heappush(sub,n)
        if not q:
            q=sub
            sub=[]
            heapq.heapify(sub)
            day+=1
            break

if conduct==set(node):
    print(day)
else:
    print(-1)

### FIXED CODE ###

N=int(input())
A=[[] for i in range(0,N)]
nodes=[]
for i in range(0,N-1):
    for j in range(i+1,N):
        nodes.append((i,j))

order={i:[0 for j in range(0,N)] for i in range(0,N)}
for i in range(0,N):
    A[i]=list(map(int,input().split()))
    for j in range(0,N-1):
        order[i][A[i][j]-1]=j
        #i番目の人がj番目の人と戦うのが何番目か


q=set([])
for battle in nodes:
    i,j=battle
    if order[i][j]==0 and order[j][i]==0:
        q.add(battle)

flag=[0 for i in range(0,N)]

day=0
sub=set([])
while q:
    while q:
        i,j=q.pop()
        flag[i]+=1
        flag[j]+=1
        if flag[i]!=N-1:
            s=A[i][order[i][j]+1]-1
            if flag[s]>=order[s][i]:
                sub.add((i,s))
        if flag[j]!=N-1:
            t=A[j][order[j][i]+1]-1
            if flag[t]>=order[t][j]:
                sub.add((j,t))

        if not q:
            day+=1
            q=sub
            sub=set([])
            break

able=True
for i in range(0,N):
    if flag[i]!=N-1:
        able=False

if able:
    print(day)
else:
    print(-1)