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

# ABC172 C
import sys
n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_CumulativeSum = [0]
B_CumulativeSum = [0]
for i in range(n):
    A_CumulativeSum.append(A[i] + A_CumulativeSum[i])
for i in range(m):
    B_CumulativeSum.append(B[i] + B_CumulativeSum[i])

if A_CumulativeSum[n-1] + B_CumulativeSum[m-1] <= k:
    print(n+m)
    sys.exit()

ans = 0
for i in range(n+1):
    time = A_CumulativeSum[i]
    if time > k:
        break
    time_b = k - time
    j = m
    while time_b < B_CumulativeSum[j]:
        j -= 1

    count = i + j
    ans = max(count, ans)

print(ans)


### FIXED CODE ###

# ABC172 C
import sys
n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A_CumulativeSum = [0]
B_CumulativeSum = [0]
for i in range(n):
    A_CumulativeSum.append(A[i] + A_CumulativeSum[i])
for i in range(m):
    B_CumulativeSum.append(B[i] + B_CumulativeSum[i])

if A_CumulativeSum[n-1] + B_CumulativeSum[m-1] <= k:
    print(n+m)
    sys.exit()

ans = 0
j = m
for i in range(n+1):
    time = A_CumulativeSum[i]
    if time > k:
        break
    time_b = k - time
    while time_b < B_CumulativeSum[j]:
        j -= 1

    count = i + j
    ans = max(count, ans)

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

a, b, c = map(int, input().split())#赤midoriao
k = int(input())
#赤＜緑＜青
if a < b and b<c:
  print("Yes")
else:
  while k > 0:
    if a >= b:
      b = b*2
      k-=1
    if b >= c and k>0:
      c = c*2
      k -=1
  if a < b and b < c:
    print("Yes")
  else:
    print("No")
    


### FIXED CODE ###

a, b, c = map(int, input().split())#赤midoriao
k = int(input())
#赤＜緑＜青
if (a < b) and (b<c):
  print("Yes")
else:
  while (a>=b) and (k>0):
    b = b*2
    k-=1
  #print(b)
  #print(k)
  while (b>=c) and (k>0):
    c = c*2
    k-=1
  #print(c)
  #print(k)
#print(a,b,c,k)
  if (a < b) and (b<c) and (k>=0):
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import itertools
N, K = list(map(int, input().split()))
poss = []
result = []
count = 0
for n in range(1, N+1):
    if (2 * n) % K == 0:
        poss.append(n)

#print(poss)
poss2 = list(itertools.product(poss, repeat=3))
#print(poss2)

for comb in poss2:
    if (comb[0]+comb[1])%K==0 and (comb[1]+comb[2])%K==0 and (comb[2]+comb[0])%K==0:
        count += 1

print(count)

### FIXED CODE ###

N, K = map(int, input().split())
num = {i%K:N//K for i in range(1, K+1)}
mod = N % K
for i in range(1, mod+1):
    num[i] += 1

ans = 0
for i in range(K):
    if (2*i) % K == 0:
        cnt = num[i]
        cnt *= num[(K-i)%K] * num[(K-i)%K]
        ans += cnt
print(ans)
### BUGGY CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    answer = 1
    limit = pow(10, 18)

    for i in range(N):
        answer *= A[i]

    if answer > limit:
        print(-1)
        exit()
    else:
        print(answer) 

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    A = sorted(A, reverse = True)
    if A[-1] == 0:
        print(0)
        exit()
        
    answer = 1
    limit = pow(10, 18)
    for i in range(N):
        answer *= A[i]
        if answer > limit:
            print(-1)
            exit()
        else:
            continue

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

N, M = map(int, readline().split())
ans = []
append_ans = ans.append
graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)

root = 1
q = [root]
append_q = q.append
checked = [0] * (N + 1)
#checked[root] = 1
order = []
append_order = order.append
parent = [-1 for _ in range(N+1)]

while q:
    x = q.pop(0)
    if checked[x]:
        continue
    checked[x] = 1
    for y in graph[x]:
        if checked[y]:
            continue
        if parent[y] != -1:
            continue
        parent[y] = x
        append_ans(x)
        append_order(y-2)
        #checked[y] = 1
        append_q(y)

if len(order) != N - 1:
    print('No')
else:
    print('Yes')
    for i in range(len(order)):
        j = order.index(i)
        print(ans[j])

### FIXED CODE ###

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

N, M = map(int, readline().split())
m = map(int, read().split())
AB = list(zip(m, m))
graph = [[] for _ in range(N+1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
q = [root]
checked = [0] * (N + 1)
checked[root] = 1
order = []
D = [0 for _ in range(N+1)]
d = 0
while q:
    x = q.pop(0)
    d = D[x]
    for y in graph[x]:
        if checked[y]:
            continue
        D[y] = d + 1
        checked[y] = 1
        q.append(y)

ans = [0 for _ in range(N+1)]
for a, b in AB:
    d_a, d_b = D[a], D[b]
    if d_a < d_b:
        ans[b] = a
    elif d_a > d_b:
        ans[a] = b

print('Yes')
print('\n'.join(map(str, ans[2:])))
### BUGGY CODE ###

#C
M = int(input())
A = list(map(int, input().split())) 
ans = [0] * M

for i in range(1,M+1):
    ans[i-1]=A.count(i)
    
for a in ans:
    print(a)

### FIXED CODE ###

#C
M = int(input())
A = list(map(int, input().split())) 
ans = [0] * M

for i in range(M-1):
    ans[int(A[i])-1]+=1
    
for a in ans:
    print(a)
### BUGGY CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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


def dfs(l):
    ret = 0
    if len(l) == 1:
        return l[0]
    elif len(l) == 0:
        return 0
    else:
        le = len(l)
        mi = min(l)
        min_ind = l.index(mi)
        ret += mi*(min_ind+1)*(le-min_ind)
        return ret + dfs(l[:min_ind])+dfs(l[min_ind+1:])


def solve():
    ans = dfs(A)
    print(ans)


def solve2():
    ans = 0
    min_cand = 1
    for i in range(N):
        prev = float('inf')
        for j in range(i, N):
            if A[j] < prev:
                prev = A[j]
                ans += prev
            else:
                ans += prev
        # if A[i] == min_cand:
         #   min_cand += 1

    print(ans)


# solve()
solve2()


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

    def same(self, x, y):
        return self.find(x) == self.find(y)


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

Un = UnionFind(N+1)
pos = [-1]*(N+1)
for i, a in enumerate(A):
    pos[a] = i

ans = 0
for i in reversed(range(1, N+1)):
    ind = pos[i]
    left = 0
    right = 0
    if ind > 0 and A[ind] < A[ind-1]:
        left = Un.size[Un.find(ind-1)]
        Un.union(ind, ind-1)
    if ind+1 < N and A[ind+1] > A[ind]:
        right = Un.size[Un.find(ind+1)]
        Un.union(ind, ind+1)
    ans += (left+1)*(right+1)*A[ind]

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

import heapq
n,m = map(int,input().split())
ls = list(map(int,input().split()))
ls = list(map(lambda x:x*(-1),ls))
di = [list(map(int,input().split())) for _ in range(m)]
heapq.heapify(ls)
for i,j in di:
    for k in range(i):
        heapq.heappush(ls,j*(-1))
ans = 0
for l in range(n):
    ans += (-1)*heapq.heappop(ls)
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
ls = list(map(int,input().split()))
di = [list(map(int,input().split())) for _ in range(m)]
fi = []
for i,j in di:
    fi.append([j,i])
for k in ls:
    fi.append([k,1])
fi.sort(reverse=True)
ans = 0
cnt = 0
how = 0
while True:
    if how + fi[cnt][1] < n:
        how += fi[cnt][1]
        ans += fi[cnt][1]*fi[cnt][0]
    else:
        ans += (n-how)*fi[cnt][0]
        break
    cnt += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
S = [0 for _ in range(H)]
ver = [[0] * W for h in range(H)]
hor = [[0] * W for h in range(H)]

for h in range(H):
    S[h] = list(input().strip())

for i, s in enumerate(S):
    c = 0
    q = []
    for k, j in enumerate(s):
        if j == '.':
            c += 1
            q.append(k)
            continue
        for qq in q:
            ver[i][qq] = c
        q = []
        c = 0
    else:
        for qq in q:
            ver[i][qq] = c

for w in range(W):
    c = 0
    q = []
    for i, s in enumerate(S):
        if s[w] == '.':
            c += 1
            q.append(i)
            continue
        for qq in q:
            hor[qq][w] = c
        q = []
        c = 0
    else:
        for qq in q:
            hor[qq][w] = c
        q = []
        c = 0

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, hor[h][w]+ver[h][w])
print(ans-1)

### FIXED CODE ###

import sys
from collections import deque
import numpy as np
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
S = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
u = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
d = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
l = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
r = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)

for h in range(H):
    s = [1 if i == '.' else 0 for i in input().strip()]
    S[h + 1] = np.array([0] + s + [0])

for h in range(1, H + 1):
    u[h] = (u[h-1] + 1) * S[h]
    d[H+1-h] = (d[H+2-h] + 1) * S[H+1-h]

for w in range(1, W + 1):
    l[:, w] = (l[:, w-1] + 1) * S[:, w]
    r[:, W+1-w] = (r[:, W+2-w] + 1) * S[:, W+1-w]

ans = u+d+l+r
print(int(ans.max()-3))
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0 for _ in range(n)]
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
	dp[i] = dp[i-1] + abs(h[i] - h[i-1])
	for j in range(1, min(i, k)+1):
		dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0 for _ in range(n)]
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
	dp[i] = dp[i-1] + abs(h[i] - h[i-1])
	for j in range(1, min(i, k)+1):
		dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

print(dp[-1])
### BUGGY CODE ###

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

res = float('inf')
for i in range(N):
    len_w = S[:i].count('W')
    len_e = S[i+1:].count('E')
    res = min(res, len_w + len_e)
    
print(res)

### FIXED CODE ###

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

W_sum = [0]
E_sum = [S.count('E')]
for i in range(0, N):
    W_sum.append(W_sum[i] + 1 if S[i] == 'W' else W_sum[i]) 
    E_sum.append(E_sum[i] - 1 if S[i] == 'E' else E_sum[i])

res = float('inf')
for i in range(0, N+1):
    res = min(res, W_sum[i] + E_sum[i])
    
print(res)
### BUGGY CODE ###

a,b,n=map(int,input().split())
m=0


for x in range(n+1):
    l=int(a*x/b)-a*int(x/b)
    
    if l>=m:

        m=l

print(m)


### FIXED CODE ###

a,b,n=map(int,input().split())
#0<=x<=b-1でfloor(x/b)は0となるので単調増加になる
#単調増加なのでb-1とnの小さいほうがxの最大値
x=min(b-1,n)

print(a*x//b)
### BUGGY CODE ###

N = int(input())

acc = 1
for i in input().split():
  acc *= int(i)

if acc > 10**18:
  print('-1')
else:
  print(acc)


### FIXED CODE ###

N = int(input())
AS = [int(i) for i in input().split()]

m = 10 ** 18
acc = 1
if 0 in AS:
  print(0)
  import sys
  sys.exit()

for i in AS:
  acc *= i
  if acc > m:
    print('-1')
    import sys
    sys.exit()

print(acc)
### BUGGY CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
ma=a[-1]
pn=[i for i in range(ma+1)]
for i in range(2,ma//2+1):
  j=2
  while j*i<=ma:
    pn[j*i]=i
    j+=1
chk=[0]*(ma+1)
for i in a:
  if i==1:
    continue
  x=pn[i]
  chk[x]+=1
  while x!=i:
    while i%x==0:
      i//=x
    x=pn[i]
    chk[x]+=1
ans=2
for i in chk:
  if i==n:
    ans=0
    break
  if i>=2:
    ans=1
if ans==2:
  print('pairwise coprime')
elif ans==1:
  print('setwise coprime')
else:
  print('not coprime')

### FIXED CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=sorted(list(map(int,input().split())))
    ma=a[-1]
    pn=[i for i in range(ma+1)]
    for i in range(2,ma//2+1):
      j=2
      while j*i<=ma:
        pn[j*i]=min(pn[j*i],i)
        j+=1
    chk=[0]*(ma+1)
    for i in a:
      if i==1:
        continue
      x=pn[i]
      chk[x]+=1
      while x!=i:
        while i%x==0:
          i//=x
        x=pn[i]
        chk[x]+=1
    ans=2
    for i in chk[2:]:
      if i==n:
        ans=0
        break
      if i>=2:
        ans=1
    if ans==2:
      print('pairwise coprime')
    elif ans==1:
      print('setwise coprime')
    else:
      print('not coprime')

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

n = int(input())
ss = []
for i in range(n):
    s = input()
    ss.append(''.join(sorted(s)))

ss = sorted(ss)

res = 0
for i in range(len(ss)-1):
    for j in range(i+1, len(ss)):
        if ss[i] == ss[j]:
            res += 1
        else:
            break

print(res)

### FIXED CODE ###

n = int(input())
ss = []
for i in range(n):
    s = input()
    ss.append(''.join(sorted(s)))

ss = sorted(ss)

res = 0
while True:
    if len(ss) <= 1:
        break
    if ss[0] != ss[1]:
        ss.pop(0)
        continue
    i = 1
    while True:
        if i == len(ss):
            res += i * (i-1) / 2
            for num in range(i):
                ss.pop(0)
            break
        if ss[0] == ss[i]:
            i += 1
        else:
            res += i * (i-1) / 2
            for num in range(i):
                ss.pop(0)
            break

print(int(res))
### BUGGY CODE ###

h, w = map(int, input().split())

a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]

c = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]

m = (h+w)*80
sets = [[set() for j in range(w)] for i in range(h)]
sets[0][0].add(c[0][0])
for i in range(1, h):
    for e in sets[i - 1][0]:
        if e <= m:
            sets[i][0].add(e + c[i][0])
            sets[i][0].add(abs(e - c[i][0]))
for i in range(1, w):
    for e in sets[0][i - 1]:
        if e <= m:
            sets[0][i].add(e+c[0][i])
            sets[0][i].add(abs(e-c[0][i]))
for i in range(1, h):
    for j in range(1, w):
        for e in sets[i-1][j]:
            if e <= m:
                sets[i][j].add(e+c[i][j])
                sets[i][j].add(abs(e - c[i][j]))
        for e in sets[i][j-1]:
            if e <= m:
                sets[i][j].add(e+c[i][j])
                sets[i][j].add(abs(e-c[i][j]))

print(min(sets[h - 1][w - 1]))

### FIXED CODE ###

h, w = map(int, input().split())

a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]

c = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]
mask = (1 << (h+w) * 80) - 1
sets = [[0 for j in range(w)] for i in range(h)]
sets[0][0] = (1 << 80+c[0][0]) | (1 << 80-c[0][0])
for i in range(1, h):
    sets[i][0] |= (sets[i - 1][0] << 80 + c[i][0]
                   ) | (sets[i - 1][0] << 80 - c[i][0])
for i in range(1, w):
    sets[0][i] |= (sets[0][i-1] << 80 + c[0][i]
                   ) | (sets[0][i-1] << 80 - c[0][i])
for i in range(1, h):
    for j in range(1, w):
        sets[i][j] |= (sets[i - 1][j] << 80 + c[i][j]
                       ) | (sets[i - 1][j] << 80 - c[i][j])
        sets[i][j] |= (sets[i][j-1] << 80 + c[i][j]
                       ) | (sets[i][j - 1] << 80 - c[i][j])
    sets[i][j] &= mask

s = bin(sets[h - 1][w - 1] + (1 << (h + w) * 80))
min_v = 1 << 80
for i in range(len(s)):
    if s[-1-i] == '1':
        min_v = min(min_v, abs(i - (h + w) * 80 + 80))
print(min_v)
### BUGGY CODE ###

from math import floor

word = input()
num = int(input())
length=len(word)
charlist_size=num*length

string_generator=(word[i%length] for i in range(charlist_size))

char_before= ''
sum=0
count= 0

for index in range(charlist_size):
    char_now=next(string_generator)
    if index == 0 :
        char_before = char_now
        count = 1
        continue
    
    if char_before == char_now :
        count = count + 1
    else:
        char_before = char_now
        sum = sum+ floor(count/2)
        count = 1
    
    if index == charlist_size-1:
        sum = sum+ floor(count/2)
    
print(sum)
        

### FIXED CODE ###

from math import floor

word = input()
num = int(input())
length=len(word)

char_before= ''
sum=0
subsum =0
count= 0
stack=[]

for index in range(length):
    char_now=word[index]
    if index == 0 :
        char_before = char_now
        char_first=char_now
        count = 1
        if length==1:
            char_last=char_now
            stack.append(count)
        continue
    
    if char_before == char_now :
        count = count + 1
    else:
        char_before = char_now
        stack.append(count)
        count = 1
    
    if index == length-1:
        char_last=char_now
        stack.append(count)

for i in stack:
    subsum= subsum + floor(i/2)
    
if (stack[0]%2)==1 and (stack[-1]%2)==1 and char_last==char_first and len(stack)>=2:
    sum =(subsum+1)*num -1
elif len(stack)==1:
    sum = floor(length*num/2)
else:
    sum =(subsum)*num

print(sum)
### BUGGY CODE ###

s=input()[::-1]
n=len(s)
p=2019
S=[0 for i in range(n+1)]
ans=[0]*p

for i in range(n):
  S[i+1]=(S[i]+(10**(i)*int(s[i]))%p)%p
  ans[S[i+1]]+=1

cnt=ans[0]
for i, a in enumerate(ans):
  if i:
  	cnt+=(a*(a-1))//2
  
print(cnt)


### FIXED CODE ###

s=input()[::-1]
p=2019
ans=[0]*p

x10, S=1, 0
for i in s:
  S+=x10*int(i)
  S%=p
  x10*=10
  x10%=p
  ans[S]+=1

cnt=ans[0]
for a in ans:
  cnt+=(a*(a-1))//2
  
print(cnt)
### BUGGY CODE ###

l1  = input().split()
ar = []
for i in l1:
  l1.append(int(i))
d = {1:0,9:0,7:0,4:0}
for i in ar:
  for j in d:
    if  i == j:
      d[j] = 1
con = True
for  i in d:
  if d[i] == 0:
    con = False
    print("NO")
    break
if con:
  print("YES")
   

### FIXED CODE ###

l1  = input().split(" ")
ar = []
for i in l1:
  ar.append(int(i))
d = {1:0,9:0,7:0,4:0}
for i in ar:
  for j in d:
    if  i == j:
      d[j] = 1
con = True
for  i in d:
  if d[i] == 0:
    con = False
    print("NO")
    break
if con:
  print("YES")
### BUGGY CODE ###

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

x = 0
i = 0

while i < len(a):
    if a[i] != i+1:
        a.pop(i)
        x+=1
        i-=1
    i+=1
    
print(x if x != n else -1)

### FIXED CODE ###

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

x = 1

for i in range(n):
    if a[i] == x:
        x += 1

print(n - x + 1 if x > 1 else -1)
### BUGGY CODE ###



from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    #nxt = defaultdict(set)
    nxt = defaultdict(list)

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

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j == 0:
                b = (l,h)
            else:
                before[(l,h)] += 1
                #nxt[b].add((l,h))
                nxt[b].append((l,h))
                b = (l,h)



    match_today = deque()

    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
                

    
    ans = 0
    cnt_match = 0 
    while match_today:
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_today.append((nl, nh))
        
       


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

### FIXED CODE ###


from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    if next_opponent[b] == a:
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で戦う相手がaではないなら、順番が来るまで待つ
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
s = 0
for i in range(n):
  a = [0]+l[:i]+l[i+1:]+[0]
  for j in range(len(a)-1):
    s += abs(a[j+1]-a[j])
  print(s)
  s = 0
  

### FIXED CODE ###

n = int(input())
l = [0]+list(map(int,input().split()))+[0]
s = 0
for j in range(len(l)-1):
    s += abs(l[j+1]-l[j])
for i in range(1,n+1):
  a = l[i-1]
  b = l[i]
  c = l[i+1]
  if a<=b<=c:
    print(s)
  elif a<=c<=b:
    print(s-2*(b-c))
  elif b<=a<=c:
    print(s-2*(a-b))
  elif b<=c<=a:
    print(s-2*(c-b))
  elif c<=a<=b:
    print(s-2*(b-a))
  elif c<=b<=a:
    print(s)
### BUGGY CODE ###

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

for i in range(n):
    wa = 0
    for j in range(n-i):
        wa += a[i+j]
        if wa == 0:
            ans += 1
        else:
            pass

print(ans)

### FIXED CODE ###

import math
n = int(input())
a = list(map(int,input().split()))
dic_S = {0:[0]}
S = 0
ans = 0
for i in range(n):
    S += a[i]
    if S not in dic_S:
        dic_S[S] = []
    else:
        pass
    dic_S[S].append(a[i])
    

for k in dic_S.keys():
    I = len(dic_S[k])
    if 3 <= I:
        ans += math.factorial(I) // (math.factorial(I-2)*2)
    elif I == 2:
        ans += 1
    else:
        pass
print(ans)
### BUGGY CODE ###

n = int(input())
for _ in range(n):
    a, b = input(), input()
    i, j = len(a), len(b)
    prev = [0] * (j + 1)
    for ca in a:
        cur = [0] * (j + 1)
        for l, cb in enumerate(b):
            if ca == cb:
                cur[l + 1] = prev[l] + 1
            else:
                cur[l + 1] = max(cur[l], prev[l + 1])
        prev = cur
    print(prev[-1])

### FIXED CODE ###

n = int(input())
for _ in range(n):
    a, b = input(), input()
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print(len(indices))