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

from collections import Counter

mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

C = Counter()
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    if c == 0:
        continue
    L *= pow(i, c, mod)
    L %= mod

print(L * sum(pow(a, mod - 2, mod) for a in A) % mod)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()
### BUGGY CODE ###

n,q=[int(i) for i in input().split()]
s=input().replace("AC","10")
f=[1 if s[i]=="1" else 0 for i in range(n)]
for i in range(q):
  l,r=[int(i)-1 for i in input().split()]
  print(sum(f[l:r]))


### FIXED CODE ###

n,q=map(int,input().split())
l=[0 for i in range(n)]
for i,v in enumerate(list(input().replace("AC","X!"))):
    l[i]=l[i-1]+(v=="!")
for c in range(q):
    h,m=map(int,input().split())
    print(l[m-1]-l[h-1])
### BUGGY CODE ###

N =int(input())
l =[int(input()) for i in range(5)]
l = l[::-1]
s=[0 for i in range(5)]
s.append(N)
ans=0

while True:
    for i in range(5):
        if s[i+1]>=l[i]:
            s[i]+=l[i]
            s[i+1]-=l[i]
        else:
            s[i]+=s[i+1]
            s[i+1]=0
    ans+=1
    if s[0]==N:
        break
print(ans)


### FIXED CODE ###

N =int(input())
l =[int(input()) for i in range(5)]
s=[N]
st=[0 for i in range(5)]
s.extend(st)
ans=0

min_num=min(l)
min_ind=l.index(min_num)

if N%min_num==0:
    times=int(N/min_num)
else:
    times=int(N/min_num)+1

dis=4
ans=times+dis

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

s = input()
a = "".join([chr(97 + i) for i in range(26)])
b = "".join([a[i - 1] for i in range(26)])
x = str.maketrans(a, b)
while True:
    s = s.translate(x)
    if "the." in s or "that." in s or "this." in s:
        print(s)
        break


### FIXED CODE ###

import sys
a = "abcdefghijklmnopqrstuvwxyz"
x = str.maketrans(a, a[1:] + a[:1])
for s in sys.stdin:
    while True:
        s = s.translate(x)
        if "the" in s or "that" in s or "this " in s:
            print(s, end = "")
            break
### BUGGY CODE ###

import bisect
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
BC = [list(map(int,input().split())) for _ in range(M)]

for b,c in BC:
    idx = bisect.bisect(A,c)
    A = A[b:idx] + [c]*b + A[idx:]
    # print(A)
print(sum(sorted(A)[-N:]))

### FIXED CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC, key=lambda x:x[1], reverse=True)
D = [0] * N
idx = 0
for b,c in BC:
    for i in range(b):
        D[idx] = c
        idx += 1
        if idx >= N:
            break
    if idx >= N:
        break
# print(D)


# print(D)
# print(sorted(A))
# print(len(D), len(A))
for i in range(N):
    if A[i] < D[i]:
        A[i] = D[i]
    else:
        break
print(sum(A))
### BUGGY CODE ###

N,M = map(int,input().split())
AB = []
ans = 0
for i in range(N):
    A,B = map(int,input().split())
    t = A,B
    AB.append(t)
    
AB.sort()

for i in range(len(AB)):
    if M < 0:
        break
    for x in range(AB[i][1]):
        if M > 0:
            ans += AB[i][0]
            M -= 1
       
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N,M=[int(x) for x in input().strip().split()]
AN=[]
BN=[]
val={}
for i in range(N):
    Ai,Bi=[int(x) for x in input().strip().split()]
    val[Ai]=Bi+val.get(Ai,0)
    AN.append(Ai)
 
AN=sorted(set(AN))
m=0
ans=0
for Ai in AN:
    ans+=Ai*min(M-m,val[Ai])
    m+=min(M-m,val[Ai])
    if m==M:
        break
print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
Ps = list(map(int, input().split()))

def hw(p):
    h,w = divmod(p-1,n)
    return h,w

def toP(h,w):
    return h * n + w + 1

fs = [[0]*n for i in range(n)]
## フロアフィールドを作る
for i in range(n):
    x = min(i,n-1-i)
    for j in range(n):
        y = min(j,n-1-j)
        fs[i][j] = min(x,y)

ans = 0
mvs = [(1,0),(-1,0),(0,1),(0,-1)]
occupied = [[1]*n for i in range(n)]

for p in Ps:
    h,w = hw(p) 
    ans += fs[h][w]
    occupied[h][w] = 0
    q = deque([])
    q.append(p)
    while len(q) > 0: #pを起点にBFS
        p_ = q.popleft()
        h, w = hw(p_)
        dist = fs[h][w]
        for dh,dw in mvs:
            if 0<=h+dh<n and 0<=w+dw<n:
                # ある位置h,wが
                # occupiedなら、隣接マス+1で到達
                # vacantなら、隣接マス+0で到達
                if dist+occupied[h][w] < fs[h+dh][w+dw]:
                    q.append(toP(h+dh,w+dw))
                    fs[h+dh][w+dw] = dist + occupied[h][w]

                
print(ans)
    
    

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(int, input().split()))
Ps = [p-1 for p in Ps]
fs = [0] * (n**2)

## フロアフィールドを作る
for x in range(n**2):
    i,j = divmod(x,n)
    x = min(i,n-1-i)
    y = min(j,n-1-j)
    fs[i*n+j] = min(x,y)

ans = 0
mvs = [1, -1, n, -n]
occupied = [1] * (n**2)
for p in Ps:
    ans += fs[p]
    occupied[p] = 0
    q = deque([])
    q.append(p)
    while len(q) > 0: #pを起点にBFS
        p_ = q.popleft()
        dist = fs[p_]
        for mv in mvs:
            if 0 <= p_+mv < n**2:
                p_next = p_ + mv
                # ある位置h,wが
                # occupiedなら、隣接マス+1で到達
                # vacantなら、隣接マス+0で到達
                if dist+occupied[p_] < fs[p_next]:
                    q.append(p_next)
                    fs[p_next] = dist + occupied[p_]

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

n, m = map(int, input().split())
route_list = [[float("inf")]*n for _ in range(n)]
lrc = [ list(map(int, input().split())) for _ in range(m) ]
for l, r, c in lrc:
  for i in range(l, r):
    for j in range(i+1, r+1):
      route_list[i-1][j-1] = min(route_list[i-1][j-1], c)
      route_list[j-1][i-1] = min(route_list[j-1][i-1], c)
  
  
node_num = n

unsearched_nodes = list(range(node_num))
distance = [float("inf")] * node_num
previous_nodes = [-1] * node_num
distance[0] = 0 

def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1
            
  
while(len(unsearched_nodes) != 0):
   
    posible_min_distance = float("inf")
    for node_index in unsearched_nodes: 
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index]
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) 
    unsearched_nodes.remove(target_min_index) 

    target_edge = route_list[target_min_index] 
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis 
                previous_nodes[index] =  target_min_index 
                
if distance[node_num - 1] == float("inf"):
  print(-1)
else:
  print(distance[node_num - 1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq

def dijkstra(start, edge):
    n = len(edge)
    dist = [float("inf")]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        if dist[v] < d:
            continue
        for nv, nd in edge[v]:
            if dist[nv] > d + nd:
                dist[nv] = d + nd
                heapq.heappush(que, (dist[nv], nv))
    return dist
  
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(1, n):
  G[i].append((i-1, 0))
for _ in range(m):
  l, r, c = map(int, input().split())
  G[l-1].append((r-1, c))

D = dijkstra(0, G)
ans = D[n-1]
if ans == float("inf"):
  ans = -1
print(ans)
### BUGGY CODE ###

n = int(input())
x, y = [int(i) for i in input().split()]

for i in range(n-1):
  t, a = [int(i) for i in input().split()]
  
  if t >= x and a >= y:
    x = t
    y = a

  else:
    c = 2
    while True:
      x_ = t * c
      y_ = a * c
      if x_ >= x and y_ >= y:
        break
      c += 1
      
    x, y = x_, y_
    
print(x+y)

### FIXED CODE ###

n = int(input())
x, y = [int(i) for i in input().split()]

for i in range(n-1):
  t, a = [int(i) for i in input().split()]
  
  if t >= x and a >= y:
    x = t
    y = a



  else:
    c = max(-(-x//t), -(-y//a))

    x = t * c
    y = a * c
    
print(x+y)
### BUGGY CODE ###

import numpy as np
from numba import njit, i8, u1, void, b1
import heapq

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch*w+cw]]
    used_map = np.full(h*w,-1,dtype=np.int64)

    #move walk
    while used_map[dh*w+dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if th+ x < 0 or tw+y < 0 or th+x >= h or tw+y >= w or road_map[th+x][tw+y] == True:
                    continue
                if x == y == 0:
                    continue
                next_n  = (th+x)*w+tw+y
                if used_map[next_n] == -1 or used_map[next_n] > tl:
                        if abs(x)+abs(y) <= 1:
                            heapq.heappush(queue,[tl,next_n])
                        else:
                            heapq.heappush(queue,[tl+1,next_n])

    print(used_map[dh*w+dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)



### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
a=list(map(int,input().split()))

s=0
e=1
ans=n
while True:
    if s==e:
      e+=1
      continue
    if s==n-1:
      
      break
    res=sum(a[s:e])
    for i in range(20):
        if res&(1<<i)!=0 and a[e]&(1<<i)!=0:
            s+=1
            ans+=(e-s)
            break
    else:
        e+=1
    if e==n:
      s+=1
      ans+=(e-s)
      e=n-1
print(ans)

### FIXED CODE ###

#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
a=list(map(int,input().split()))

s=0
e=1
ans=n
acc=[0]*(n+1)
for i in range(n):
  acc[i+1]=acc[i]+a[i]
while True:
    if s==e:
      e+=1
      continue
    if s==n-1:
      
      break
    res=acc[e]-acc[s]
    for i in range(20):
        if res&(1<<i)!=0 and a[e]&(1<<i)!=0:
            s+=1
            ans+=(e-s)
            break
    else:
        e+=1
    if e==n:
      s+=1
      ans+=(e-s)
      e=n-1
print(ans)
### BUGGY CODE ###

#!/usr/bin/python
# -*- coding: utf-8 -*-

# 入力はstringで入る．
# intにしたければ int(input())
# floatで受け取ると 1.0 になる．

# 入力 : N
# 入力 : A1 A2 ... AN
N = int(input())
A = list(map(int, input().split()))

Number = []
Total = 0

for i in range(N):
    Number.append(A.count(i+1))
    Total += Number[i]*(Number[i]-1)/2

for Ak in A:
    print(int(Total - Number[Ak-1]+1))


### FIXED CODE ###


import collections

# 入力 : N
# 入力 : A1 A2 ... AN
N = int(input())
A = list(map(int, input().split()))

C = collections.Counter(A)

Total = sum([i*(i-1)/2 for i in C.values()])

for Ak in A:
    print(int(Total - C[Ak]+1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

edges = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

q = [0]

ans = [-1]*n
ans[0] = 0
count = 1

while q:
    l = q.pop(0)
    for i in edges[l]:
        if ans[i] == -1:
            ans[i] = l
            count += 1
            q.append(i)
    if count == n:
        break

if count == n:
    print('Yes')
    for i in ans[1:]:
        print(i+1)
else:
    print('No')


### FIXED CODE ###

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

edges = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

q = [0]

ans = [-1]*n
ans[0] = 0
count = 1

while q:
    l = q.pop(0)
    for i in edges[l]:
        if ans[i] == -1:
            ans[i] = l
            count += 1
            q.append(i)
    if count == n:
        break

if count == n:
    print('Yes')
    for i in ans[1:]:
        print(i+1)
else:
    print('No')
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())),reverse=True)
score = [A[0]]
s = 0

for i in range(1,N):
    s += score[0]
    score = score[1:] + [A[i],A[i]]

print(s)

### FIXED CODE ###

import math
N = int(input())
A = sorted(list(map(int, input().split())),reverse=True)
s = A[0]

for i in range(1,N-1):
    s += A[math.ceil(i/2)]

print(s)
### BUGGY CODE ###

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

kabu = 0
money = 1000
for i in range(n):
    if i == n-1:
        money += kabu*a[i]
        kabu = 0
    elif a[i] < a[i+1]:
        while money >= a[i]:
            kabu += 1
            money -= a[i]
    else:
        money += kabu*a[i]
        kabu = 0
    
print(money)
    

### FIXED CODE ###

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

kabu = 0
money = 1000
for i in range(n):
    if i == n-1:
        money += kabu*a[i]
        kabu = 0
    elif a[i] < a[i+1]:
        if money >= a[i]:
            kabu = money // a[i]
            money = money - a[i]*kabu
    else:
        money += kabu*a[i]
        kabu = 0
    
print(money)
### BUGGY CODE ###

n, k, q = map(int, input().split())
a = [int(input()) - 1 for i in range(q)]

nl = [k for i in range(n)]

for i in a:
    nl = [j-1 for j in nl]
    nl[i] += 1

for i in range(n): 
    if nl[i] > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

n, k, q = map(int, input().split())
a = [int(input()) - 1 for i in range(q)]

nl = [k-q for i in range(n)]

for i in a:
    nl[i] += 1

for i in range(n): 
    if nl[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

def main():
  n = int(input())
  base = []
  base_ans = []

  for i in range(n):
    temp = 0
    s = input()
    sign = 0
  
    for j in range(10):
      temp  = temp + 10**(ord(s[j]) - 97)
    
    for j in range(len(base)):
      if temp == base[j][0]:
        base[j][1] = base[j][1] + 1
        sign = 1
      
    if sign == 0:
      base.append([temp,1])

  ans = 0
  for i in range(len(base)):
    if base[i][1] >= 2:
      ans = ans + base[i][1]*(base[i][1] - 1)//2
      
  print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  n = int(input())
  mydict = {}

  for i in range(n):
    temp = list(input())
    temp.sort()
    temp = ''.join(temp)
    
    if temp not in mydict:
      mydict[temp] = 1
    else:
      mydict[temp] =  mydict[temp] + 1
      
  ans = 0
  for i in mydict.values():
    if i >= 2:
      ans = ans + i*(i-1)//2
    
  print(ans)
  
if __name__ == '__main__':
    main()
### BUGGY CODE ###

K,S = map(int,input().split())

cnt =0
for a in range(K+1):
  for b in range(K+1):
    for c in range(K+1):
      if a+b+c == S:
        cnt += 1
        
print(cnt)  

### FIXED CODE ###

K,S = map(int,input().split())

cnt = 0
for a in range(K+1):
  for b in range(K+1):
    if S-a-b>=0 and S-a-b<=K:
      cnt += 1
        
print(cnt)
### BUGGY CODE ###

from collections import defaultdict, deque
import sys

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def d(n):
    divisors = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    return divisors


def main():
    N = int(input())
    # A = [
    #     int(input())
    #     for _ in range(N)
    # ]
    A = [int(a) for a in input().split()]

    res_c = 0
    res1 = []
    bucket = [0] * (N + 1)

    for i in reversed(range(N)):
        k = i + 1
        if i * 2 + 2 > N:
            if A[i] == 1:
                res_c += 1
                res1.append(k)
                for di in d(k):
                    bucket[di] += 1
            continue
        if k == 1:
            if res_c % 2 != A[i]:
                res_c += 1
                res1.append(k)
            break

        if bucket[k] % 2 != A[i]:
            res_c += 1
            res1.append(k)
            for di in d(k):
                bucket[di] += 1
    print(res_c)
    print(*res1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, deque
import sys

sys.setrecursionlimit(100000)

MIN = -10 ** 9
MAX = 10 ** 9 + 7


def d(n):
    divisors = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i * i != n:
                divisors.append(n // i)

    return divisors


def main():
    N = int(input())
    # A = [
    #     int(input())
    #     for _ in range(N)
    # ]
    A = [int(a) for a in input().split()]

    res1 = []
    bucket = [0] * (N + 1)

    i = N
    for Ai in reversed(A):
        i -= 1
        k = i + 1
        if k * 2 > N:
            if Ai == 1:
                res1.append(k)
                bucket[k] = 1

            continue
        if k == 1:
            if len(res1) % 2 != Ai:
                res1.append(k)
            break

        s = 0
        j = 0
        while True:
            j+=1
            if j * k > N:
                break
            s += bucket[j * k]

        if s % 2 != Ai:
            res1.append(k)
            bucket[k] = 1
    print(len(res1))
    print(*res1)


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

# coding: utf-8
import bisect

N,M,L=map(int, raw_input().split())
Roads = [] # from, to, cost
for i in range(M):
    Roads.append(map(int, raw_input().split()))
Q=int(raw_input())
Queries = [] # from, to
for i in range(Q):
    Queries.append(map(int, raw_input().split()))

def dijkstra(s, t):

    candidates = [[s,0,0]] # node, charge, used
    candidates_val = [0]

    while candidates:
        cn, cc, cu = candidates.pop(0)
        candidates_val.pop(0)
        if cn == t:
            return cc
        for fi, ti, ci in Roads:
            if fi == cn:
                node = ti
            elif ti == cn:
                node = fi
            else:
                continue

            if ci > L:
                continue
            elif cu + ci > L:
                charge = cc + 1
                used = ci
            else:
                charge = cc
                used = ci + cu

            cost = charge * L + used
            idx = bisect.bisect_left(candidates_val, cost)
            candidates_val.insert(idx, cost)
            candidates.insert(idx, [node, charge, used])
    return -1

for s,t in Queries:
    print dijkstra(s,t)


### FIXED CODE ###

# coding: utf-8
from scipy.sparse.csgraph import floyd_warshall

N,M,L=map(int, input().split())
RG=[[0 for i in range(N)] for j in range(N)]

for i in range(M):
    f,t,c = map(int, input().split())
    if c <= L:
        RG[f-1][t-1] = c
        RG[t-1][f-1] = c

Rd = floyd_warshall(RG, directed=False)

FG=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i+1, N):
        if Rd[i][j] <= L:
            FG[i][j] = 1
            FG[j][i] = 1

Fd = floyd_warshall(FG, directed=False)

Q=int(input())
for i in range(Q):
    s, t = map(int, input().split())
    v = Fd[s-1][t-1]
    if s == t:
        print (str(0))
    if v == float('inf'):
        print (str(-1))
    else:
        print (str(int(v-1)))
### BUGGY CODE ###

import sys
from collections import defaultdict, deque
sys.setrecursionlimit(10**9)
N = int(input())
es = defaultdict(list)
se = defaultdict(list)
ins = [0]*(N*(N-1)//2)
dp = [-1]*(N*(N-1)//2)
ID = [[0]*N for i in range(N)]
count = 0
for i in range(N):
  for j in range(N):
    if i<j:
      ID[i][j] = count
      count += 1
def TP_sort(E, ins, start):
  q = deque(start)
  res = []
  while q:
    p = q.popleft()
    res += [p]
    for c in E[p]:
      ins[c] -= 1
      if ins[c]==0:
        q.append(c)
  for i in ins:
    if i>0:
      return -1
  return res

def dfs(e):
  if dp[e]!=-1:
    return dp[e]
  m = 0
  for ex in se[e]:
    x = dfs(ex)
    if x>m:
      m = x
  dp[e] = m+1
  return m+1

for i in range(N):
  inf = [int(i)-1 for i in input().split()]
  for j in range(N-2):
    x = min(i, inf[j])
    y = max(i, inf[j])
    nx = min(i, inf[j+1])
    ny = max(i, inf[j+1])
    t = ID[x][y]
    nt = ID[nx][ny]
    es[t] += [nt]
    se[nt] += [t]
    ins[nt] += 1
start = [v1 for v1 in range(len(ins)) if ins[v1]==0]
ls = TP_sort(es, ins, start)
if ls==-1:
  print(-1)
else:
  for i in start:
    dp[i] = 0
  print(dfs(ls[-1])+1)


### FIXED CODE ###

N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)