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

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 左側A[:k] (N<=k<=2*N)までの最大値を求める
# 同様に右側も求める
N = ir()
A = lr()
left_sum = [0] * (N+1)
right_sum = [0] * (N+1)
left = A[:N]; heapify(left)
right = A[-N:]
right = [-x for x in right]
heapify(right)
left_sum[0] = sum(left)
center = A[N:-N]
for i in range(N):
    heappush(left, center[i])
    heappop(left)
    left_sum[i+1] = sum(left)

right_sum[N] = sum(right)
for i in range(N):
    heappush(right, -center[N-1-i])
    heappop(right)
    right_sum[N-1-i] = sum(right)

answer = -10 ** 15
for i in range(N+1):
    temp = left_sum[i] + right_sum[i]
    if temp > answer:
        answer = temp

print(answer)
# 05


### FIXED CODE ###

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 左側A[:k] (N<=k<=2*N)までの最大値を求める
# 同様に右側も求める
N = ir()
A = lr()
left_sum = [0] * (N+1)
right_sum = [0] * (N+1)
left = A[:N]; heapify(left)
right = A[-N:]
right = [-x for x in right]
heapify(right)
cur = sum(left)
left_sum[0] = cur
center = A[N:-N]
for i in range(N):
    heappush(left, center[i])
    l = heappop(left)
    cur = cur - l + center[i]
    left_sum[i+1] = cur

cur = sum(right)
right_sum[N] = cur
for i in range(N):
    heappush(right, -center[N-1-i])
    r = heappop(right)
    cur = cur - r + (-center[N-1-i])
    right_sum[N-1-i] = cur

answer = -10 ** 15
for i in range(N+1):
    temp = left_sum[i] + right_sum[i]
    if temp > answer:
        answer = temp

print(answer)
# 05
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit
def solve(N, costX, costY):
    ans = [INF] * (N + 1)

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = np.minimum(cx, cy).sum()
        ans[M] = min(ans[M], cost)

    return ans

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    XYP.sort(key=lambda xyp: xyp[2], reverse=False)

    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]

    def calcCost(AP, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    ans = solve(N, costX, costY)
    print(*ans, sep='\n')

sol()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)


N, Q = map(int, input().split())
AB = [[] for i in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    AB[a - 1].append(b - 1)

X = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    X[p - 1] += x


def recursive(p):
    for c in AB[p]:
        X[c] += X[p]
        recursive(c)


recursive(0)
print(" ".join(map(str, X)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)


N, Q = map(int, input().split())
AB = [[] for i in range(N + 1)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    AB[a].append(b)

X = [0] * (N + 1)
for _ in range(Q):
    p, x = map(int, input().split())
    X[p] += x


def recursive(p):
    for c in AB[p]:
        X[c] += X[p]
        recursive(c)


recursive(1)
print(" ".join(map(str, X[1:])))
### BUGGY CODE ###

import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 'S':
        break
ans = min([i, H - 1 - i, j, W - 1 - j])
Q = collections.deque([[i, j, K, ans]])
while Q:
    h, w, res, dist = Q.popleft()
    A[h][w] = '#'
    ans = min([ans, h, H - 1 - h, w, W - 1 - w])
    if ans == 0:
        print(1)
        exit()
    if res:
        res -= 1
        if h and A[h - 1][w] == '.':
            Q += [[h - 1, w, res, ans]]
        if h < H - 1 and A[h + 1][w] == '.':
            Q += [[h + 1, w, res, ans]]
        if w and A[h][w - 1] == '.':
            Q += [[h, w - 1, res, ans]]
        if w < W - 1 and A[h][w + 1] == '.':
            Q += [[h, w + 1, res, ans]]
print(1 + math.ceil(ans / K))


### FIXED CODE ###

import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for h in range(H):
    if 'S' in A[h]:
        w = A[h].index('S')
        break
visited = [[False] * W for _ in range(H)]
ans = min([h, H - 1 - h, w, W - 1 - w])
res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and not visited[h][w]:
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]
print(1 + math.ceil(ans / K))
### BUGGY CODE ###

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

r = 0
asum = [0]

for i in A:
    asum.append(asum[-1] + i)    

for i in range(len(A)):
    Axor = A[i]
    for j in range(i, len(A)):
        if ( i == j ):
            r += 1
        else:
            Axor = Axor ^ A[j]      
            if (asum[j+1] - asum[i]) == Axor:
                r += 1

print(r)

### FIXED CODE ###

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

res = 0
asum = [0]
axor = [0]

for i in A:
    asum.append(asum[-1] + i)
    axor.append(axor[-1] ^ i)

for l in range(N):
    ok = l+1
    ng = N+1
    while(ng - ok > 1):
        r = (ok + ng) // 2
        s = (axor[r] ^ axor[l])
        t = (asum[r] - asum[l])
        if s == t:
            ok = r
        else:
            ng = r
    
    res += ok - l
         
print(res)
### BUGGY CODE ###

n =int(input())
a=[]
b=[]
c=[]
a =list(map(int,input().split()))
a.sort()
b =list(map(int,input().split()))
b.sort()
c =list(map(int,input().split()))
c.sort()
b_limit = 0
c_limit =0
count =0

for i in a:
    if b_limit == 1:
        break
    for j in  reversed(b):
        if j <= i:
            if j == max(b):
                b_limit +=1
            break
        for k in reversed(c):
            if k <= j:
                break
            count +=1

print(count)



### FIXED CODE ###

import bisect

ans =0

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

for i in b:
    s = bisect.bisect_right(c,i)
    s_num = n-s

    t = bisect.bisect_left(a,i)
    t_num = t

    ans += s_num * t_num

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

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    from math import sqrt
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)
    A = set(A)
    if c[1] == 1:
        return print(1)
    elif c[1] > 1:
        return print(0)

    ans = 0
    for a in A:
        if a in bl:
            continue
        ok = True
        for i in range(2, int(a**0.5)+1):
            if a % i == 0:
                if i in A:
                    ok = False
                if a//i in A:
                    ok = False
            if not ok:
                break
        if ok:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    B = [True]*(10**6+1)

    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)

    ans = 0
    for a in set(A):
        if a not in bl and B[a]:
            ans += 1
        for i in range(1, 10**6):
            if 10**6 < a*i:
                break
            B[a*i] = False
    print(ans)


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

X,Y,Z,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
B=[int(i) for i in input().split(" ")]
C=[int(i) for i in input().split(" ")]

delicious=[]

A=sorted(A,reverse=True)
B=sorted(B,reverse=True)
C=sorted(C,reverse=True)

for i in range(min(K,len(A))):
    for j in range(min(K,len(B))):
        for k in range(min(K,len(C))):
            delicious.append(A[i]+B[j]+C[k])

delicious=sorted(delicious,reverse=True)
for i in range(K):
    print(delicious[i])


### FIXED CODE ###

import heapq
X,Y,Z,K=[int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
B=[int(i) for i in input().split(" ")]
C=[int(i) for i in input().split(" ")]

AB=[]
for a in A:
    for b in B:
        AB.append(a+b)

AB=heapq.nlargest(K,AB)
ABC=[]
for ab in AB:
    for c in C:
        ABC.append(ab+c)

for cake in heapq.nlargest(K,ABC):
    print(cake)
### BUGGY CODE ###

import sys
import numpy as np
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = np.full((n+1, w+1), -1)

def rec(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == n:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)

n,w = (int(x) for x in input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]
dp = [[0] * (w+1) for _ in range(n+1)]

def rec(i, j):
  if dp[i][j] != 0:
    return dp[i][j]
  if i == n:
    res = 0
  elif j < a[i][0]:
    res = rec(i+1, j)
  else:
    res = max(rec(i+1, j), rec(i+1, j - a[i][0]) + a[i][1])
  dp[i][j] = res
  return dp[i][j]

print(int(rec(0, w)))
### BUGGY CODE ###

import fractions

A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

cd = set()
i = 1
while i * i <= gcd:
    if gcd % i == 0:
        cd.add(i)
        cd.add(gcd//i)
    i += 1

ans = set()
for n in sorted(cd):
    if n == 1:
        continue
    for j in ans:
        if n**(j-1) % j == 0:
            break
    else:
        ans.add(n)

print(len(ans)+1)


### FIXED CODE ###

import fractions
import heapq

A,B = map(int,input().split())
gcd = fractions.gcd(A,B)

cd = []
for i in range(1, int(gcd**0.5)+1):
    if gcd % i == 0:
        heapq.heappush(cd, i)
        i2 = gcd//i
        if i != i2:
            heapq.heappush(cd, i2)

heapq.heappop(cd)

ans = set()
for i in range(len(cd)):
    n = heapq.heappop(cd)
    for j in ans:
        if n % j == 0:
            break
    else:
        ans.add(n)

print(len(ans)+1)
### BUGGY CODE ###

def readinput():
    n=int(input())
    return n

def main(n):
    sum=0
    while(n>0):
        sum+=n%10
        n=n//10
    if sum%9==0:
        return 'Yes'
    else:
        return 'No'

if __name__=='__main__':
    n=readinput()
    ans=main(n)
    print(ans)


### FIXED CODE ###

def readinput():
    n=input()
    return n

def main(n):
    sum=0
    j=len(n)-1
    while(j>=0):
        sum+=int(n[j])
        j-=1
    if sum%9==0:
        return 'Yes'
    else:
        return 'No'

if __name__=='__main__':
    n=readinput()
    ans=main(n)
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)
# import time

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


MOD = 998244353

N = d_in()
# start_time = time.time()
total = 3 ** N - (2**N - 2) * 3 - 3

a_list = []
for _ in range(N):
    a_list.append(d_in())
sum_a = sum(a_list)

# 1要素目: i番目の整数までを考慮
# 2要素目: [both>0, 緑>0&青==0, 緑==0&青>0, both==0]
# 3要素目: 最大の色(赤とする)の和
dp = np.zeros((N+1, 4, 1 + (sum_a+1)//2), dtype=int)
dp[0, 3, 0] = 1

for i in range(1, N+1):
    # a = d_in()
    # sum_a += a
    # 赤に入れる
    a = a_list[i-1]
    dp[i, :, a:] += dp[i-1, :, :-a]
    dp[i, :, -1] += dp[i-1, :, -a:].sum(axis=1)

    # 緑に入れる
    dp[i, 0, :] += dp[i-1, 0, :]
    dp[i, 0, :] += dp[i-1, 2, :]
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 3, :]

    # 青に入れる
    dp[i, 0, :] += dp[i-1, 0, :]
    dp[i, 0, :] += dp[i-1, 1, :]
    dp[i, 2, :] += dp[i-1, 2, :]
    dp[i, 2, :] += dp[i-1, 3, :]

    # # まとめる ---> 数ms...あまり寄与せず
    # dp[:, i, 0] = dp[:, i, 0] + dp[:, i-1, 0]*2 + dp[:, i-1, 2] + dp[:, i-1, 1]
    # dp[:, i, 1] = dp[:, i, 1] + dp[:, i-1, 1] + dp[:, i-1, 3]
    # dp[:, i, 2] = dp[:, i, 2] + dp[:, i-1, 2] + dp[:, i-1, 3]

    if i % 15 == 0:
        dp %= MOD

dp %= MOD
print((total - dp[-1, 0, -1].sum() * 3) % MOD)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)
# import time

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


MOD = 998244353

N = d_in()
total = 3 ** N - (2**N - 2) * 3 - 3

a_list = []
for _ in range(N):
    a_list.append(d_in())
sum_a = sum(a_list)

# 1要素目: i番目の整数までを考慮
# 2要素目: [both>0, 緑>0&青==0, 緑==0&青>0, both==0]
# 3要素目: 最大の色(赤とする)の和
dp = np.zeros((N+1, 3, 1 + (sum_a+1)//2), dtype=int)
dp[0, 2, 0] = 1

for i in range(1, N+1):
    # 赤に入れる
    a = a_list[i-1]
    dp[i, :, a:] += dp[i-1, :, :-a]
    dp[i, :, -1] += dp[i-1, :, -a:].sum(axis=1)

    # 緑or青に入れる
    dp[i, 0, :] += (dp[i-1, 0, :] + dp[i-1, 1, :]) * 2
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 2, :]

    if i % 10 == 0:
        dp[i, :, :] %= MOD

print((total - dp[-1, 0, -1] * 3) % MOD)
### BUGGY CODE ###

N = int(input())
S = list(input())
 
cnt = []
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            s = S[i] + S[j] + S[k]
            cnt.append(s)

print(len(set(cnt)))

### FIXED CODE ###

N = int(input())
S = list(input())
PIN = []
b1 = []
for i in range(N-2):
    b2 = []
    if S[i] in b1:
        continue
    else:
        b1.append(S[i])
    for j in range(i+1, N-1):
        b3 = []
        if S[j] in b2:
            continue
        else:
            b2.append(S[j])
        for k in range(j+1, N):
            if S[k] in b3:
                continue
            else:
                b3.append(S[k])
            cand = S[i] + S[j] + S[k]
            PIN.append(cand)

print(len(set(PIN)))
### BUGGY CODE ###

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

def kouyaku(n,p):
    for i in range(round((p**(1/n)+1)),0,-1):
        if p%(i**n)==0:
            return i
            
print(kouyaku(n,p))

### FIXED CODE ###

N, P = map(int, input().split())
ans = 1
 
if N >= 45:
  print(ans)
elif N == 1:
  print(P)
  
 
  
else:
  i = 1
  while(i**N <= P):
    if P % (i**N) == 0:
      ans = i
    i += 1
  print(ans)
### BUGGY CODE ###

def main():
    N, u, v = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    d_from_u = [-1] * N
    d_from_v = [-1] * N

    def dfs(v, d):
        todo = []
        d[v] = 0
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in G[u]:
                if 0 <= d[next_v]:
                    continue
                d[next_v] = d[u] + 1
                todo.append(next_v)
                break
            else:
                todo.pop()

    u, v = u-1, v-1
    dfs(u, d_from_u)
    dfs(v, d_from_v)
    ans = 0
    for du, dv in zip(d_from_u, d_from_v):
        if du < dv and ans < dv - 1:
            ans = dv - 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, u, v = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    d_from_u = [-1] * N
    d_from_v = [-1] * N

    def dfs(v, d):
        todo = []
        d[v] = 0
        todo.append(v)
        while todo:
            u = todo.pop()
            for next_v in G[u]:
                if 0 <= d[next_v]:
                    continue
                d[next_v] = d[u] + 1
                todo.append(next_v)

    u, v = u-1, v-1
    dfs(u, d_from_u)
    dfs(v, d_from_v)
    ans = 0
    for du, dv in zip(d_from_u, d_from_v):
        if du < dv and ans < dv - 1:
            ans = dv - 1
    print(ans)


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

a,b,n=map(int,input().split())
import math
x=b-1
m=[math.floor(a*n/b)-a*(math.floor(n/b))]
while x<=n:
    f=math.floor(a*x/b)-a*(math.floor(x/b))
    m.append(f)
    x+=b
print(max(m))

### FIXED CODE ###

a,b,n=map(int,input().split())
import math
if n<b:
    m=math.floor(a*n/b)
else:
    e=b-1
    m=math.floor(a*e/b)
print(m)
### BUGGY CODE ###

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

O = A.copy()

O = [k for k in O if O.count(k) == 1]

for i in A:
    for j in A:
        if i != j:
            if (i%j == 0):
                if i in O:
                    O.remove(i)

ans = len(O)

print(ans)

### FIXED CODE ###

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


mx = max(A)
x = [0] * (mx + 1) # len(x)
for i in A:
    x[i] += 1
for i in range(1, mx + 1):
    if x[i] != 0:
        for j in range(2 * i, mx + 1, i):
            x[j] = 0
    if x[i] > 1:
        x[i] = 0
print(sum(x))
### BUGGY CODE ###

S = input()
Q = int(input())
r_count = 0
for query in range(Q):
  query = list(input().split())
  t = query[0]
  if (t == '1'):
    r_count += 1
  elif (t == '2'):
    f = query[1]
    new_S = ""
    if(f == '1' and (r_count % 2 == 0)):
      new_S = query[2] + S
    elif(f == '1' and (r_count % 2 == 1)):
      new_S = S + query[2]
    elif(f == '2' and (r_count % 2 == 0)):
      new_S = S + query[2]
    elif(f == '2' and (r_count % 2 == 1)):
      new_S = query[2] + S
    S = new_S

if (r_count % 2 == 1):
  for i, s in enumerate(reversed(S)):
    if (i == len(S) - 1):
      print(s)
    else:
      print(s, end="")
else:
  print(S)


### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())

r_count = 0
for query in range(Q):
  query = deque(list(input().split()))
  t = query[0]
  if (t == '1'):
    r_count += 1
  elif (t == '2'):
    f = query[1]
    if(f == '1' and (r_count % 2 == 0)):
      S.appendleft(query[2])
    elif(f == '1' and (r_count % 2 == 1)):
      S.append(query[2])
    elif(f == '2' and (r_count % 2 == 0)):
      S.append(query[2])
    elif(f == '2' and (r_count % 2 == 1)):
      S.appendleft(query[2])

if (r_count % 2 == 1):
  for i, s in enumerate(reversed(S)):
    if (i == len(S) - 1):
      print(s)
    else:
      print(s, end="")
else:
  for i, s in enumerate(S):
    if (i == len(S) - 1):
      print(s)
    else:
      print(s, end="")
### BUGGY CODE ###


def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [list(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    flag = [True]*N
    min_id = 0
    while(min_id < N-1):
        ans += 1
        if ans > (N*(N-1)) // 2:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    if Lock[A[i][id[i]]-1] == i and i not in tmp:
                        Lock[A[i][id[i]]-1] = -1
                        id[A[i][id[i]]-1] += 1
                        tmp.add(A[i][id[i]]-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > (N*(N-1)) // 2:
        print(-1)
    else:
        print(ans)


main()


### FIXED CODE ###

def main():
    import sys
    import time
    input = sys.stdin.buffer.readline
    start = time.time()
    N = int(input())
    A = [tuple(map(int, input().split())) for i in range(N)]

    id = [0]*N
    Lock = [-1]*N
    ans = 0
    min_id = 0
    M = (N*(N-1)) // 2

    while(min_id < N-1):
        now = time.time()
        if now - start > 1.9:
            ans = M
            break
        ans += 1
        if ans > M:
            break
        tmp = set()
        for i in range(N):
            if id[i] >= N-1:
                continue
            else:
                if Lock[i] >= 0:
                    continue
                else:
                    a = A[i][id[i]]
                    if Lock[a-1] == i and i not in tmp:
                        Lock[a-1] = -1
                        id[a-1] += 1
                        tmp.add(a-1)
                        id[i] += 1
                    else:
                        if i not in tmp:
                            Lock[i] = A[i][id[i]]-1
        min_id = min(id)
    if ans > M:
        print(-1)
    else:
        print(ans)


main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
l = [''.join(sorted(list(input())))]
cnt = 0
for i in range(N-1):
    s = ''.join(sorted(list(input())))
    cnt += l.count(s)
    l.append(s)
print(cnt)

### FIXED CODE ###

import collections
from itertools import combinations
import sys
input = sys.stdin.readline

N = int(input())
s = [''.join(sorted(list(input()))) for _ in range(N)]
c = collections.Counter(s)

cnt = 0
for i in c.values():
    if i > 1:
        cnt += i*(i-1)//2
print(cnt)
### BUGGY CODE ###

from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
B = list(accumulate([0] + A[1::2] + A[::2] + A[1::2] + A[::2]))
C = [S - 2 * (B[i+N//2] - B[i]) for i in range(N)]
print(*sum(list(map(list, zip(C[:N//2+1], C[N//2+1:]+[0]))), [])[:-1])

### FIXED CODE ###

from itertools import accumulate
N = int(input())
A = list(map(int, input().split()))
X1 = sum(A) - 2 * sum(A[1::2])


def g():
    state = X1
    yield X1
    for i in range(N-1):
        state = 2 * A[i] - state
        yield state


print(*list(g()))